Skip to main content
Talentd

Maximum Sum of Alternating Subsequence With Distance at Least K - Solution & Explanation

HardArrayDynamic ProgrammingSegment Tree13 min readAsked at: Visa
Practice this problem

Problem Statement

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] < ..., or
    • nums[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].

  • The distance condition holds because 2 - 0 = 2 >= k.
  • The values are strictly alternating because 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].

  • The distance condition holds because each pair of consecutive chosen indices differs by at least k = 1.
  • The values are strictly alternating since 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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= n

Approach Overview

Problem 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.

Solution

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:

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

  • State f[i][1] (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):

  • BIT bit_0: indexed by value, maintains the prefix maximum of f[cdot][0], used to query cases where nums[j] < nums[i].
  • BIT bit_1: 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)$.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SubsequencesO(2^n)O(n)Only for very small arrays or conceptual understanding
Dynamic Programming with Nested ScanO(n^2)O(n)When constraints are small and implementation simplicity matters
DP with Prefix Maximum OptimizationO(n)O(n)Best general solution for large inputs; avoids repeated scans

Video Solution

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 →

Frequently Asked Questions

Is Maximum Sum of Alternating Subsequence With Distance at Least K easy or hard?
The problem is classified as Hard because it combines two constraints: alternating subsequence sums and a minimum index distance. Recognizing the DP state transitions is manageable, but optimizing the naive O(n^2) approach to O(n) using prefix maxima is the key challenge.
Maximum Sum of Alternating Subsequence With Distance at Least K Python/Java solution
Most implementations use two DP arrays (add and sub) and variables storing the best prefix values. Python solutions typically iterate once through the array while updating prefix maxima. Java and C++ follow the same logic with arrays or long variables to track the best alternating states.
How to solve Maximum Sum of Alternating Subsequence With Distance at Least K in O(n)?
Track two DP arrays: add[i] for subsequences ending at i with a plus operation and sub[i] for those ending with a minus operation. Maintain prefix maximum values for add and sub among indices ≤ i − k. Use these to compute transitions add[i] = nums[i] + bestSub and sub[i] = -nums[i] + bestAdd. Updating prefix maxima as indices become eligible keeps the algorithm linear.
What is the best approach for Maximum Sum of Alternating Subsequence With Distance at Least K?
The most efficient approach uses dynamic programming with prefix maximum optimization. Maintain two states: one where the current element is added and one where it is subtracted. By tracking the best previous values whose indices are at least k away, each transition becomes O(1). This reduces the total complexity to O(n) time with O(n) space.
Is Maximum Sum of Alternating Subsequence With Distance at Least K asked at Google/Amazon/Meta?
Alternating subsequence and constrained subsequence DP problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving index gaps, alternating sums, or prefix optimizations are common because they test dynamic programming fundamentals and optimization of repeated range queries.
What data structure is used in Maximum Sum of Alternating Subsequence With Distance at Least K?
The core solution uses dynamic programming arrays along with prefix maximum tracking. No complex structure is required if you maintain rolling maximum values as indices become valid. In some variations, segment trees or heaps can replace prefix maxima when the valid range is more complex.
What is the time complexity of Maximum Sum of Alternating Subsequence With Distance at Least K?
The optimal solution runs in O(n) time using dynamic programming with prefix maxima. Each index is processed once, and previous valid states are retrieved in constant time. A straightforward DP implementation without optimization takes O(n^2) time because it scans all earlier indices satisfying the distance constraint.

Ready to solve this problem?

Practice Maximum Sum of Alternating Subsequence With Distance at Least K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays