# 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], prices[indexes], ..., 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 - indexes = 4 - 2 = 2.
prices - prices = 7 - 5 = 2.
For j = 3, we have:
indexes - indexes = 5 - 4 = 1.
prices - prices = 8 - 7 = 1.
The sum of the elements is: prices + prices + prices = 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

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

func max(a, b int64) int64 {
if a > b {
return a
}
return b
}

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