Problem

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 themaximum score that a linear selection can have.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: prices = [1,5,3,7,8]
Output: 20
Explanation: We can select the indexes [2,4,5]. We show that our selection is linear:
For j = 2, we have:
indexes[2] - indexes[1] = 4 - 2 = 2.
prices[4] - prices[2] = 7 - 5 = 2.
For j = 3, we have:
indexes[3] - indexes[2] = 5 - 4 = 1.
prices[5] - prices[4] = 8 - 7 = 1.
The sum of the elements is: prices[2] + prices[4] + prices[5] = 20.
It can be shown that the maximum sum a linear selection can have is 20.

Example 2:

1
2
3
4

Input: prices = [5,6,7,8,9]
Output: 35
Explanation: We can select all of the indexes [1,2,3,4,5]. Since each element has a difference of exactly 1 from its previous element, our selection is linear.
The sum of all the elements is 35 which is the maximum possible some out of every selection.

Constraints:

  • 1 <= prices.length <= 10^5
  • 1 <= prices[i] <= 10^9

Solution

Method 1 – Hash Map for Linear Difference

Intuition

For a linear selection, the difference between price and day index must be constant for all selected elements. For each possible difference (prices[i] - i), we can collect the sum of all prices with that difference. The answer is the maximum such sum.

Approach

  1. For each index i (1-indexed), compute diff = prices[i] - i.
  2. Use a hash map to accumulate the sum of prices for each diff.
  3. The answer is the maximum value among all accumulated sums.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int maxLinearStockScore(vector<int>& prices) {
        unordered_map<int, int> mp;
        int n = prices.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            mp[prices[i] - (i+1)] += prices[i];
            ans = max(ans, mp[prices[i] - (i+1)]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxLinearStockScore(prices []int) int {
    mp := map[int]int{}
    ans := 0
    for i, v := range prices {
        d := v - (i+1)
        mp[d] += v
        if mp[d] > ans {
            ans = mp[d]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxLinearStockScore(int[] prices) {
        Map<Integer, Integer> mp = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < prices.length; ++i) {
            int d = prices[i] - (i+1);
            mp.put(d, mp.getOrDefault(d, 0) + prices[i]);
            ans = Math.max(ans, mp.get(d));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxLinearStockScore(prices: IntArray): Int {
        val mp = mutableMapOf<Int, Int>()
        var ans = 0
        for (i in prices.indices) {
            val d = prices[i] - (i+1)
            mp[d] = mp.getOrDefault(d, 0) + prices[i]
            ans = maxOf(ans, mp[d]!!)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maxLinearStockScore(self, prices: list[int]) -> int:
        from collections import defaultdict
        mp: dict[int, int] = defaultdict(int)
        ans = 0
        for i, v in enumerate(prices):
            d = v - (i+1)
            mp[d] += v
            ans = max(ans, mp[d])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn max_linear_stock_score(prices: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut mp = HashMap::new();
        let mut ans = 0;
        for (i, &v) in prices.iter().enumerate() {
            let d = v - (i as i32 + 1);
            *mp.entry(d).or_insert(0) += v;
            ans = ans.max(*mp.get(&d).unwrap());
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxLinearStockScore(prices: number[]): number {
        const mp: Record<number, number> = {}
        let ans = 0
        for (let i = 0; i < prices.length; ++i) {
            const d = prices[i] - (i+1)
            mp[d] = (mp[d] ?? 0) + prices[i]
            ans = Math.max(ans, mp[d])
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each price once.
  • 🧺 Space complexity: O(n), for the hash map storing sums for each difference.