Watch 2 video solutions for Maximum Linear Stock Score, a medium level problem involving Array, Hash Table. This walkthrough by Programming Live with Larry has 171 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.
Example 1:
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:
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 <= 1051 <= prices[i] <= 109Problem Overview: You are given an array of stock prices. The goal is to pick a subsequence of days whose prices follow a specific linear relationship and maximize the total score (sum of selected prices). The key observation is that valid pairs of indices must satisfy a fixed linear difference between the price and the index.
Approach 1: Brute Force Pair Expansion (O(n2) time, O(1) space)
The most direct strategy checks relationships between pairs of indices. For every starting index i, iterate over later indices j and verify whether the linear constraint prices[j] - prices[i] == j - i holds. If the condition matches, both elements belong to the same valid linear chain, so you accumulate their values into the current score. This approach explicitly compares pairs and grows groups by scanning forward. While easy to reason about, it requires nested iteration across the array, leading to O(n2) time. Space usage remains O(1) because only counters are stored.
Approach 2: Hash Table Grouping (O(n) time, O(n) space)
The linear relationship can be rewritten as prices[j] - j = prices[i] - i. This means every valid element in the same scoring chain shares the same value of prices[k] - k. Instead of comparing pairs, compute this value for each index and group elements with the same key. A hash table stores the cumulative score for each key. As you iterate through the array once, calculate key = prices[i] - i, then add prices[i] to the sum stored for that key. Track the maximum sum seen across all groups. This converts the pairwise relationship into a grouping problem, removing the nested loop. The result is O(n) time with O(n) space for the map.
The core insight is recognizing the invariant price - index. Once you derive this transformation, the problem becomes a simple aggregation task using a hash table. Each group represents a potential linear sequence, and the best score is the largest accumulated sum.
Recommended for interviews: The hash table grouping approach is the expected solution. Interviewers want to see the algebraic transformation that turns the pair constraint into a constant key (price - index). Mentioning the brute force method shows you understand the raw relationship, but deriving the O(n) grouping strategy demonstrates strong pattern recognition and practical use of hash-based aggregation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Expansion | O(n^2) | O(1) | Useful for understanding the linear relationship and validating the condition during initial problem exploration |
| Hash Table Grouping (price - index) | O(n) | O(n) | Best general solution; groups elements with identical linear offsets using a hash map |