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:
1 <= t < m, it+1 - it >= k.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 = 2
Output: 7
Explanation:
An optimal choice is indices [0, 2], which gives values [5, 2].
2 - 0 = 2 >= k.5 > 2.The score is 5 + 2 = 7.
Example 2:
Input: nums = [3,5,4,2,4], k = 1
Output: 14
Explanation:
An optimal choice is indices [0, 1, 3, 4], which gives values [3, 5, 2, 4].
k = 1.3 < 5 > 2 < 4.The score is 3 + 5 + 2 + 4 = 14.
Example 3:
Input: nums = [5], k = 1
Output: 5
Explanation:
The only valid subsequence is [5]. A subsequence with 1 element is always strictly alternating, so the score is 5.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1051 <= k <= nProblem Overview: Given an array, select a subsequence where consecutive chosen indices differ by at least k. The subsequence contributes an alternating sum: first element added, second subtracted, third added, and so on. Your goal is to maximize the resulting value.
Approach 1: Brute Force Enumeration (Exponential Time, O(2^n) time, O(n) space)
Generate every subsequence and filter those where consecutive indices differ by at least k. For each valid subsequence, compute the alternating sum by toggling between addition and subtraction. Track the maximum across all candidates. This method directly models the problem but quickly becomes infeasible as n grows because the number of subsequences doubles at each step. Useful only for validating small test cases or building intuition about the alternating pattern.
Approach 2: Dynamic Programming with Pair Transitions (O(n^2) time, O(n) space)
Define two DP states for each index i. add[i] represents the best alternating sum ending at i where nums[i] is added, and sub[i] represents the best sum ending at i where nums[i] is subtracted. For every i, scan previous indices j such that i - j ≥ k. Transition with add[i] = nums[i] + sub[j] and sub[i] = -nums[i] + add[j]. This enforces both the alternating pattern and the distance constraint. The nested loop makes the runtime quadratic, which may struggle when n is large.
Approach 3: Optimized DP with Prefix Maximum (O(n) time, O(n) space)
The transition only needs the maximum valid previous state where the index difference is at least k. Instead of scanning all previous j, maintain prefix maxima for the best add and sub values whose indices are ≤ i - k. When processing index i, compute add[i] = nums[i] + bestSubPrefix and sub[i] = -nums[i] + bestAddPrefix. After index i becomes eligible (when future indices reach i + k), update the prefix maxima. This converts the quadratic scan into constant-time transitions while still respecting the distance constraint.
The technique is a classic dynamic programming optimization: convert repeated range scans into tracked aggregates. Similar ideas appear in problems that maintain rolling maxima or use monotonic structures in array processing and advanced algorithm design.
Recommended for interviews: Start by describing the O(n^2) DP since it clearly models the alternating transitions and distance rule. Then optimize it using prefix maxima to reach O(n) time. Interviewers typically expect this optimization because it demonstrates recognition of repeated range queries and the ability to compress them into constant-time updates.
State Definition
Let f[i][0] denote the maximum sum of a valid subsequence ending at index i where the last element is a valley (the next element must be larger to maintain alternation), and f[i][1] denote the maximum sum where the last element is a peak (the next element must be smaller).
Transitions
When transitioning, we enumerate a predecessor index j satisfying j leq i - k:
f[i][0] (valley): transitions from f[j][1], requiring nums[j] > nums[i], i.e., query the maximum f[cdot][1] over the value range (nums[i],\ +infty):$f[i][0] = nums[i] + max!\left(0,\ max_{\substack{j leq i-k \ nums[j] > nums[i]}} f[j][1]\right)
(peak): transitions from f[j][0], requiring nums[j] < nums[i], i.e., query the maximum f[cdot][0] over the value range [1,\ nums[i]-1]:f[i][1] = nums[i] + max!\left(0,\ max_{\substack{j leq i-k \ nums[j] < nums[i]}} f[j][0]\right)
The final answer is max_{0 leq i < n}max(f[i][0],\ f[i][1]).
Optimization
The transitions involve dynamic prefix/suffix maximum queries over a value domain, which can be maintained efficiently with two Binary Indexed Trees (BITs):
: indexed by value, maintains the prefix maximum of f[cdot][0], used to query cases where nums[j] < nums[i].: indexed by M + 1 - val (reversed, where M = max(nums) ), maintains the prefix maximum of f[cdot][1], equivalent to a suffix maximum over the value domain, used to query cases where nums[j] > nums[i].To ensure only indices j leq i - k participate in transitions, when processing index i, we insert the state of index i - k into the BITs using a sliding pointer.
The time complexity is O(n log M) and the space complexity is O(M), where n is the length of the array and M = max(nums)$.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequences | O(2^n) | O(n) | Only for very small arrays or conceptual understanding |
| Dynamic Programming with Nested Scan | O(n^2) | O(n) | When constraints are small and implementation simplicity matters |
| DP with Prefix Maximum Optimization | O(n) | O(n) | Best general solution for large inputs; avoids repeated scans |
Super Hard💀DP + Segment Tree asked by Leetcode in Weekly Contest 499(Q4,3915) • Kumar K [Amazon] • 1,000 views views
Watch 3 more video solutions →Practice Maximum Sum of Alternating Subsequence With Distance at Least K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor