Maximum linear stock score

Array Hash Table

61.6% acceptance

Mar 31, 2026

Given a 1-indexed integer array prices, where prices[i] is the price of a particular stock on the ith day, your task is to select some of the elements of prices such that your selection is linear. A selection indexes, where indexes is a 1-indexed integer array of length k which is a subsequence of the array [1, 2, ..., n], is linear if: For every 1 < j <= k, prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]. A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. The score of a selection indexes, is equal to the sum of the following array: [prices[indexes[1]], prices[indexes[2]], ..., prices[indexes[k]]. Return the maximum score that a linear selection can have.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(prices: Vec<i32>) -> i64 {
    let mut groups: std::collections::HashMap<i64, i64> = std::collections::HashMap::new();
    for (i, &p) in prices.iter().enumerate() {
      let key = p as i64 - i as i64;
      *groups.entry(key).or_insert(0) += p as i64;
    }
    *groups.values().max().unwrap()
  }
}