Maximum linear stock score
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]
The score of a linear selection is the sum of the prices at those indices, return the maximum score that a linear selection can have given the input.
The essential idea is that a linear sequence has the property prices[i] - i = prices[j] - j
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;
}
}Related Problems
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.