Skip to main content
Talentd

Maximum Linear Stock Score - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash Table8 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

 

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 <= 105
  • 1 <= prices[i] <= 109

Approach Overview

Problem 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.

Solution

We can transform the equation as follows:

$ prices[i] - i = prices[j] - j

In fact, the problem is to find the maximum sum of all prices[i] under the same prices[i] - i.

Therefore, we can use a hash table cnt to store the sum of all prices[i] under the same prices[i] - i, and finally take the maximum value in the hash table.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the prices$ array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ExpansionO(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

Video Solution

2898. Maximum Linear Stock Score (Leetcode Medium) • Programming Live with Larry • 171 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Linear Stock Score easy or hard?
Maximum Linear Stock Score is typically considered a Medium difficulty problem. The challenge is recognizing that the pair condition can be rewritten as price - index, which enables an efficient hash map grouping solution.
Maximum Linear Stock Score Python/Java solution
Both Python and Java implementations use a hash map to accumulate sums for each (price - index) key. Iterate through the array, compute the key, update the map, and maintain the maximum score. The algorithm runs in O(n) time and O(n) space.
How to solve Maximum Linear Stock Score in O(n)?
Compute a key for each element using price - index. Use a hash map where the key stores the running sum of prices for that group. Iterate through the array once, update the group sum, and track the maximum score across all groups.
What is the best approach for Maximum Linear Stock Score?
The optimal approach groups elements by the value (price - index) using a hash table. If two elements share the same value, they satisfy the linear condition required by the problem. By summing prices within each group and tracking the maximum, the solution runs in O(n) time with O(n) space.
Is Maximum Linear Stock Score asked at Google/Amazon/Meta?
Problems involving hash map grouping and index-based transformations are common in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the pattern of converting pair constraints into a hash key appears frequently.
What data structure is used in Maximum Linear Stock Score?
A hash table (hash map) is the primary data structure. It maps the value (price - index) to the cumulative score of all elements sharing that linear offset.
What is the time complexity of Maximum Linear Stock Score?
The optimal solution runs in O(n) time because the array is processed once and each hash map operation is O(1) on average. Space complexity is O(n) to store cumulative sums for each unique (price - index) key.

Ready to solve this problem?

Practice Maximum Linear Stock Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays