Question

2898. 最大线性股票得分

English Version

题目描述

给定一个 1-indexed 整数数组 prices，其中 prices[i] 是第 i 天某只股票的价格。你的任务是 线性 地选择 prices 中的一些元素。

一个选择 indexes，其中 indexes 是一个 1-indexed 整数数组，长度为 k，是数组 [1, 2, ..., n] 的子序列，如果以下条件成立，那么它是 线性 的：

• 对于每个 1 < j <= k，prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]。

数组的 子序列 是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

选择 indexes 的 得分 等于以下数组的总和：[prices[indexes[1]], prices[indexes[2]], ..., prices[indexes[k]]。

返回 _线性选择的 最大得分。_

 

示例 1：

输入： prices = [1,5,3,7,8]
输出： 20
解释： 我们可以选择索引[2,4,5]。我们可以证明我们的选择是线性的：
对于j = 2，我们有：
indexes[2] - indexes[1] = 4 - 2 = 2。
prices[4] - prices[2] = 7 - 5 = 2。
对于j = 3，我们有：
indexes[3] - indexes[2] = 5 - 4 = 1。
prices[5] - prices[4] = 8 - 7 = 1。
元素的总和是：prices[2] + prices[4] + prices[5] = 20。 
可以证明线性选择的最大和是20。

示例 2：

输入： prices = [5,6,7,8,9]
输出： 35
解释： 我们可以选择所有索引[1,2,3,4,5]。因为每个元素与前一个元素的差异恰好为1，所以我们的选择是线性的。
所有元素的总和是35，这是每个选择的最大可能总和。

 

提示：

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

解法

方法一：哈希表

我们可以将式子进行变换，得到：

$$ prices[i] - i = prices[j] - j $$

题目实际上求的是相同的 $prices[i] - i$ 下，所有 $prices[i]$ 的和的最大值和。

因此，我们可以用一个哈希表 $cnt$ 来存储 $prices[i] - i$ 下，所有 $prices[i]$ 的和，最后取哈希表中的最大值即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $prices$ 的长度。

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