We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Linear Stock Score

Number: 3182

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a 1-indexed integer array prices where prices[i] represents the stock price on the i-th day, we need to select a subsequence of indices that is considered linear. A selection (i.e. a list of indices) is linear if for every adjacent pair, the difference between prices equals the difference between their indices. The score is defined as the sum of the selected prices, and the aim is to find the maximum possible score from any linear selection.

Key Insights

  • The linear condition: For every adjacent pair of selected indices i and j, prices[j] - prices[i] must equal j - i. This implies that prices[i] - i remains constant across the selected indices.
  • Group the indices by the value of (prices[i] - i).
  • For each group, the best possible linear selection is to take all indices that share the same (prices[i] - i). The score for that group is the sum of the prices at those indices.
  • The answer is the maximum score among all such groups.

Space and Time Complexity

Time Complexity: O(n) where n is the number of days (prices.length).
Space Complexity: O(n) for storing the sums by group key in a hash table.

Solution

We can solve the problem by noticing that the condition for a linear selection forces prices[i] - i to be the same for all selected indices. Thus, we iterate through the prices, calculate the key value (prices[i] - i) for each index, and accumulate the sum of prices for each key in a hash table (or dictionary). Finally, return the maximum sum from the hash table.

Data Structures and Approach:

  • Use a hash table (or dictionary in Python, Map in JavaScript/Java) to group the values by (prices[i] - i).
  • Loop through the entire array and update the sum for each group.
  • Return the highest sum value from the hash table.

This approach is efficient with a linear time complexity.

Code Solutions

# Python solution:
def maximumLinearStockScore(prices):
    # Dictionary to store the total price sum for each key (price - index)
    group_sum = {}
    n = len(prices)
    # Loop over each price, adjusting for 1-indexing
    for i in range(1, n + 1):
        # Compute the key using the current index i and price at i-1 (adjust for 0-indexing)
        key = prices[i - 1] - i
        # Add the current price to the corresponding group
        if key in group_sum:
            group_sum[key] += prices[i - 1]
        else:
            group_sum[key] = prices[i - 1]
    # Return the maximum sum from any group
    return max(group_sum.values())

# Example Usage:
# prices = [1, 5, 3, 7, 8]
# print(maximumLinearStockScore(prices))  # Output: 20
← Back to All Questions