LeetCode Problem 2898

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

LeetCode 2898 - Maximum Linear Stock Score

Problem Understanding

We are given a 1-indexed array prices, where prices[i] represents the stock price on day i.

We want to choose a subsequence of indices, not necessarily contiguous, such that the selected indices satisfy a special linearity condition. For every pair of consecutive selected indices:

$$prices[indexes[j]] - prices[indexes[j-1]] = indexes[j] - indexes[j-1]$$

The score of a selection is simply the sum of all selected stock prices. Our goal is to find the maximum possible score among all valid linear selections.

To understand the condition better, suppose we select two indices a and b with a < b.

The requirement becomes:

$$prices[b] - prices[a] = b - a$$

Rearranging:

$$prices[b] - b = prices[a] - a$$

This reveals the key property of the problem. Any two consecutive selected elements must have the same value of:

$$prices[i] - i$$

Because the condition must hold for every adjacent pair in the selection, every selected index must belong to the same group defined by the value:

$$prices[i] - i$$

The output should therefore be the maximum sum obtainable by selecting any subset of indices that share the same prices[i] - i value.

The constraints are important:

• n ≤ 100,000
• prices[i] ≤ 1,000,000,000

A solution that examines all subsequences is completely infeasible. We need a near-linear solution.

Some important edge cases include:

• An array containing only one element.
• Arrays where every index belongs to a different group.
• Arrays where all indices belong to the same group.
• Very large price values, requiring 64-bit integer arithmetic for the answer.

Approaches

Brute Force

A brute force solution would enumerate all possible subsequences.

For each subsequence, we would verify whether the linearity condition holds between every adjacent pair of selected indices. If the subsequence is valid, we compute its score and update the maximum.

This approach is correct because it explicitly checks every possible selection. However, an array of length n has 2^n subsequences, making this approach completely impractical even for modest values of n.

With n = 100,000, exhaustive enumeration is impossible.

Key Insight

Starting from the linearity condition:

$$prices[b] - prices[a] = b - a$$

we can rearrange it as:

$$prices[b] - b = prices[a] - a$$

This means any two consecutive selected elements must have the same value of prices[i] - i.

Furthermore, if multiple indices share the same value of prices[i] - i, then any pair among them automatically satisfies the condition:

$$prices[j] - prices[i] = (j + c) - (i + c) = j - i$$

where c is the common value of prices[k] - k.

Therefore:

• Every valid linear selection consists entirely of indices from one group.
• Every subset of a group is valid.
• Since all prices are positive, the best choice for a group is to take every element in that group.

The problem becomes:

1. Group indices by prices[i] - i.
2. Sum all prices within each group.
3. Return the largest group sum.

A hash map is perfect for maintaining these group sums.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n)	O(n)	Enumerates all subsequences
Optimal	O(n)	O(n)	Group by prices[i] - i and track sums

Algorithm Walkthrough

1. Create a hash map where the key is prices[i] - i and the value is the total score accumulated for that group.
2. Iterate through the array once.
3. For each position i, compute its grouping key. Since the array is conceptually 1-indexed, the key is:

$$prices[i] - (i + 1)$$

when using 0-indexed programming languages. 4. Add the current price to the sum stored for that key. 5. After processing all elements, every hash map entry contains the score obtained by selecting all indices belonging to that group. 6. Return the maximum value stored in the hash map.

Why it works

The crucial invariant is that every valid linear selection must contain only indices whose values of prices[i] - i are identical. Conversely, any collection of indices sharing the same value of prices[i] - i automatically satisfies the linearity condition. Since all prices are positive integers, taking every element in a group always produces the maximum score for that group. Therefore, the optimal answer is simply the largest group sum.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxScore(self, prices: List[int]) -> int:
        group_sum = defaultdict(int)

        for i, price in enumerate(prices, start=1):
            key = price - i
            group_sum[key] += price

        return max(group_sum.values())

The implementation directly follows the mathematical observation.

A defaultdict(int) stores the cumulative score for each group. The loop uses enumerate(..., start=1) so that the index matches the problem's 1-indexed definition.

For each element, we compute price - i, which uniquely identifies its group. The current price is added to the group's running sum.

After processing the entire array, each map entry contains the score achieved by selecting all indices from that group. The maximum of these sums is returned.

Go Solution

func maxScore(prices []int) int64 {
	groupSum := make(map[int]int64)
	var answer int64

	for i, price := range prices {
		key := price - (i + 1)

		groupSum[key] += int64(price)

		if groupSum[key] > answer {
			answer = groupSum[key]
		}
	}

	return answer
}

The Go solution uses a map[int]int64 to store group sums.

The answer is maintained during iteration, eliminating the need for a second pass through the map. Since the total score can exceed the range of a 32-bit integer, int64 is used for all accumulated sums.

Worked Examples

Example 1

Input:

prices = [1,5,3,7,8]

Compute the grouping key price - index.

Index	Price	Price - Index	Group Sum After Update
1	1	0	{0: 1}
2	5	3	{0: 1, 3: 5}
3	3	0	{0: 4, 3: 5}
4	7	3	{0: 4, 3: 12}
5	8	3	{0: 4, 3: 20}

Final groups:

Key	Sum
0	4
3	20

Maximum score:

20

Example 2

Input:

prices = [5,6,7,8,9]

Index	Price	Price - Index	Group Sum After Update
1	5	4	{4: 5}
2	6	4	{4: 11}
3	7	4	{4: 18}
4	8	4	{4: 26}
5	9	4	{4: 35}

Final groups:

Key	Sum
4	35

Maximum score:

35

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(n)	Hash map may contain up to n distinct groups

The algorithm performs exactly one iteration over the input array. Each hash map insertion and lookup is expected O(1), producing an overall O(n) running time. In the worst case, every element belongs to a different group, resulting in O(n) additional space.

Test Cases

from typing import List

s = Solution()

assert s.maxScore([1, 5, 3, 7, 8]) == 20      # Example 1
assert s.maxScore([5, 6, 7, 8, 9]) == 35      # Example 2

assert s.maxScore([10]) == 10                 # Single element

assert s.maxScore([1, 2, 3, 4]) == 10         # All belong to same group

assert s.maxScore([1, 10, 20, 30]) == 30      # Every element separate

assert s.maxScore([4, 2, 5, 3]) == 5          # Multiple singleton groups

assert s.maxScore([2, 4, 6, 8]) == 8          # Distinct groups only

assert s.maxScore([3, 5, 7, 6, 8]) == 15      # Best group not contiguous

assert s.maxScore([1000000000, 1000000000]) == 1000000000  # Large values

assert s.maxScore([5, 6, 10, 11]) == 21       # Two groups, second larger

Test Summary

Test	Why
[1,5,3,7,8]	Official example
[5,6,7,8,9]	Entire array forms one group
[10]	Minimum size input
[1,2,3,4]	All indices share the same key
[1,10,20,30]	Every element forms its own group
[4,2,5,3]	Multiple singleton groups
[2,4,6,8]	No profitable grouping
[3,5,7,6,8]	Optimal group is a subsequence
[1000000000,1000000000]	Large value handling
[5,6,10,11]	Competing groups with different sums

Edge Cases

Single Element Array

When the array contains only one element, that element alone forms a valid linear selection. There are no adjacent selected elements, so the linearity condition is vacuously satisfied. The algorithm creates one group and returns its sum.

Every Element Belongs to a Different Group

Consider an array where all values of prices[i] - i are distinct. In this situation, no two indices can be selected together while preserving linearity. Each group contains exactly one element. The hash map stores one entry per element, and the algorithm correctly returns the largest individual price.

All Elements Belong to the Same Group

If every element has the same value of prices[i] - i, then every index can be selected. Since all prices are positive, taking the entire array is optimal. The algorithm accumulates all prices into a single hash map entry and returns their total sum.

Very Large Price Values

Each price can be as large as 10^9, and there can be 10^5 elements. The total score may reach 10^14, which exceeds 32-bit integer limits. The Go solution uses int64 for accumulation, and Python integers naturally support arbitrary precision, ensuring correctness for the largest inputs.