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.

Description Hints 5 Solution Video 11:37

2898. Maximum Linear Stock Score

Medium62.3% acceptance1 companyPremium elsewhere, free here

Given a 1-indexed integer array prices, where prices[i] is the price of a particular stock on the i^th 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 <= 10⁵
1 <= prices[i] <= 10⁹

Asked at 1 company

Amazon

Topics

Array Hash Table

Hints open one at a time

Hint 1

Let's look at the condition as: prices[indexes[i]] - indexes[i] == prices[indexes[j]] - indexes[j].

Hint 2

So now we define a new array named group and is constructed as group[i] = prices[i] - i.

Hint 3

A subarray of prices is linear if they belong to the same group.

Hint 4

Since all elements are positive, if we choose some index i, the optimum way is to choose all elements from group[i].

Hint 5

So for each group, we calculate the sum of its prices and the answer would be the maximum sum over all groups.

11:37

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,5,3,7,8]

Input

[5,6,7,8,9]

Your code is saved on this device.Solution