Maximum Sum of Alternating Subsequence With Distance at Least K
You are given an integer array nums of length n and an integer k.
Pick a subsequence with indices 0 <= i1 < i2 < ... < im < n such that:
- For every
1 <= t < m,it+1 - it >= k. - The selected values form a strictly alternating sequence. In other words, either:
nums[i1] < nums[i2] > nums[i3] < ..., ornums[i1] > nums[i2] < nums[i3] > ...
A subsequence of length 1 is also considered strictly alternating. The score of a valid subsequence is the sum of its selected values.
Return an integer denoting the maximum possible score of a valid subsequence.
Example 1
Input
nums = [5,4,2], k = 2Output
7An optimal choice is indices
[0, 2], giving values [5, 2], which satisfy the distance condition and are strictly alternating, for a score of 7.Example 2
Input
nums = [3,5,4,2,4], k = 1Output
14An optimal choice is indices
[0, 1, 3, 4], giving values [3, 5, 2, 4], which satisfy the distance condition and alternate strictly, for a score of 14.Constraints
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^5
- 1 <= k <= n