Coding

Maximum Linear Stock Score

Asked at

Arista Networks

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Your job is to choose some of the elements of prices so that your selection is linear given a 1-indexed integer array of prices, where prices[i] is the price of a certain stock on the ith day.

The following conditions must be met for a selection indexes, which is a 1-indexed integer array of length k and a subsequence of the array [1, 2,..., n], to be linear:

Prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1] for each 1 < j <= k.

An array that may be created from another array by removing part or all of its items without altering the order of the remaining components is called a subsequence.

The total of the following arrays determines a selection index's score: [prices[indexes[1]], prices[indexes[2]],..., prices[indexes[k]].

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.

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.

Input : prices = [7, 2, 4, 2, 6, 1]

1 <= prices.length <= 105
1 <= prices[i] <= 109

cpp

class Solution{
    public:
        long long maxScore(vector<int>& prices) {
            //your code goes here
        }
};

java

class Solution {
    public long maxScore(int[] prices) {
        //your code goes here
    }
}

python

class Solution:
    def maxScore(self, prices):
        #your code goes here

javascript

class Solution {
    maxScore(prices) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public long MaxScore(int[] prices)
    {
        //your code goes here
    }
}

func maxScore(prices []int) int64 {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Rewrite the adjacent condition algebraically.
02Observe that selected elements share `prices[i] - i`.
03Accumulate the best positive score for each key.
04Update the global maximum.
05Use 64-bit sums.

Reference answer

For two selected indices a < b, the condition prices[b] - prices[a] = b - a is equivalent to prices[b] - b = prices[a] - a. Therefore every member of a valid linear subsequence belongs to one group keyed by prices[i] - i (use the problem's one-indexed index consistently). Within one key, any indices preserve the condition pairwise, so the best score is the sum of all positive prices in that group; a negative item can be skipped because the selection is a subsequence. Maintain a map from key to accumulated positive sum and update the answer as each price arrives. If the specification requires choosing at least one item, initialize from individual values too. This is O(N) expected time, O(N) space, and requires long long for scores.

Then expect these follow-ups

What changes if the subsequence must be non-empty?
Tests: edge cases
Can sorting replace the map?
Tests: tradeoffs

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question