Maximum Linear Stock Score

Maximum Linear Stock Score

What is this problem about?

The Maximum Linear Stock Score coding problem gives you an array of stock prices. A "linear group" of stocks consists of indices forming a subset where the prices form an arithmetic sequence with the same difference as their index difference — specifically, prices[i] - i is the same for all indices in the group. You want to find the maximum sum of prices over all such linear groups.

Why is this asked in interviews?

Amazon includes this problem to test the ability to identify a hidden grouping key. The key insight is that prices[i] - i = constant defines a group, transforming the problem into a hash-map grouping task. Candidates who spot this mathematical equivalence can solve it in O(n); others who try to find arithmetic subsequences the hard way struggle. This tests mathematical observation as much as coding.

Algorithmic pattern used

The solution uses a hash map grouping approach. For each index i, compute key = prices[i] - i. Group all indices with the same key together. For each group, the sum of prices[i] values is a candidate answer. Return the maximum group sum. The transformation prices[i] - i captures the "linearity" condition: if two indices i and j are in the same group, prices[i] - prices[j] = i - j, meaning the prices differ by exactly the index difference (slope 1).

Example explanation

Prices: [1, 5, 3, 7, 9], indices 0-4.

• keys: 1-0=1, 5-1=4, 3-2=1, 7-3=4, 9-4=5.
• Group key=1: indices 0,2 → prices 1,3 → sum=4.
• Group key=4: indices 1,3 → prices 5,7 → sum=12.
• Group key=5: index 4 → price 9 → sum=9.
• Maximum = 12.

The group {index 1, index 3} has prices {5, 7}. Price difference = 2, index difference = 2. Linear! Sum = 12.

Common mistakes candidates make

• Trying to enumerate all arithmetic subsequences: O(n²) or worse. Missing the key transformation makes the problem much harder than it is.
• Using prices[i] / i as key: Division introduces floating point issues and doesn't correctly represent the linear relationship. Always use subtraction.
• Confusing "linear" with "sorted": The stock prices don't need to be sorted; they just need to follow the index-proportional relationship.

Interview preparation tip

For the Array Hash Table interview pattern, practice spotting mathematical invariants that define grouping. When a problem mentions "arithmetic progression" or "same slope," look for a subtraction or ratio that's constant within the group. This hash-map grouping technique solves many "find maximum sum of equivalent groups" problems in O(n).