Question

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.

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())

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;
  }
};

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)
  }
}