Welcome to Subscribe On Youtube

2898. Maximum Linear Stock Score

Description

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

Solutions

Solution 1: Hash Table

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.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public long maxScore(int[] prices) {
          Map<Integer, Long> cnt = new HashMap<>();
          for (int i = 0; i < prices.length; ++i) {
              cnt.merge(prices[i] - i, (long) prices[i], Long::sum);
          }
          long ans = 0;
          for (long v : cnt.values()) {
              ans = Math.max(ans, v);
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      long long maxScore(vector<int>& prices) {
          unordered_map<int, long long> cnt;
          for (int i = 0; i < prices.size(); ++i) {
              cnt[prices[i] - i] += prices[i];
          }
          long long ans = 0;
          for (auto& [_, v] : cnt) {
              ans = max(ans, v);
          }
          return ans;
      }
  };
  

• class Solution:
      def maxScore(self, prices: List[int]) -> int:
          cnt = Counter()
          for i, x in enumerate(prices):
              cnt[x - i] += x
          return max(cnt.values())
  
  

• func maxScore(prices []int) (ans int64) {
  	cnt := map[int]int{}
  	for i, x := range prices {
  		cnt[x-i] += x
  	}
  	for _, v := range cnt {
  		ans = max(ans, int64(v))
  	}
  	return
  }
  

• function maxScore(prices: number[]): number {
      const cnt: Map<number, number> = new Map();
      for (let i = 0; i < prices.length; ++i) {
          const j = prices[i] - i;
          cnt.set(j, (cnt.get(j) || 0) + prices[i]);
      }
      return Math.max(...cnt.values());
  }
  
  

• use std::collections::HashMap;
  
  impl Solution {
      pub fn max_score(prices: Vec<i32>) -> i64 {
          let mut cnt: HashMap<i32, i64> = HashMap::new();
  
          for (i, x) in prices.iter().enumerate() {
              let key = (*x as i32) - (i as i32);
              let count = cnt.entry(key).or_insert(0);
              *count += *x as i64;
          }
  
          *cnt.values().max().unwrap_or(&0)
      }
  }
  
  

All Problems

All Solutions