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.
Solutions for this problem are being prepared.
Try solving it yourself| 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 |
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