LeetCode Problem 3409

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

LeetCode 3409 - Longest Subsequence With Decreasing Adjacent Difference

Problem Understanding

We are given an array nums, and we want to choose a subsequence from it. A subsequence preserves the original order of elements but may skip arbitrary positions.

For a chosen subsequence

$$seq_0, seq_1, seq_2, \dots, seq_m$$

we look at the absolute differences between consecutive elements:

$$|seq_1-seq_0|, |seq_2-seq_1|, \dots, |seq_m-seq_{m-1}|$$

The requirement is that these differences must form a non-increasing sequence:

$$|seq_1-seq_0| \ge |seq_2-seq_1| \ge \dots \ge |seq_m-seq_{m-1}|$$

Our goal is to find the maximum possible length of such a subsequence.

The constraints are important:

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 300

The array can contain up to ten thousand elements, which is too large for any exponential or quadratic-state-over-indices dynamic programming approach.

However, the values themselves are very small. Every number lies between 1 and 300. This suggests that a solution should exploit the small value range rather than the potentially large array length.

Several edge cases are worth noticing immediately:

• A subsequence of length 2 is always valid because there is only one difference.
• Repeated values create differences of 0, which are perfectly valid.
• The optimal subsequence may skip many elements.
• Multiple previous values can produce the same difference, so we must always keep the best possible state.
• The decreasing condition applies to differences, not to the numbers themselves. The sequence values may increase or decrease arbitrarily.

Approaches

Brute Force

A brute-force solution would enumerate every subsequence and check whether its adjacent differences form a non-increasing sequence.

For each subsequence, we would:

1. Compute all adjacent absolute differences.
2. Verify that the differences are non-increasing.
3. Track the maximum valid length.

This approach is correct because it explicitly checks every possible subsequence.

Unfortunately, an array of length n has 2^n subsequences. Even for relatively small values of n, this becomes completely infeasible. With n = 10^4, the approach is impossible.

Key Insight

The critical observation is that the values are bounded:

$$1 \le nums[i] \le 300$$

Therefore:

$$0 \le |a-b| \le 299$$

There are only 300 possible values and only 300 possible differences.

Instead of tracking states by array index, we can track states by:

• the value at which a subsequence ends,
• the last adjacent difference used.

Suppose a subsequence currently ends with value v and its last difference is d.

If we want to append a new value x, the new difference becomes:

$$nd = |x-v|$$

The subsequence remains valid only if:

$$d \ge nd$$

Therefore, when extending a state, we need to know the best subsequence ending at value v whose last difference is at least nd.

This leads naturally to dynamic programming over values and differences.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(2^n \cdot n)$	$O(n)$	Enumerates all subsequences
Optimal DP	$O(n \cdot 300)$	$O(300 \cdot 300)$	Exploits small value range

Algorithm Walkthrough

State Definition

Let:

$$dp[v][d]$$

represent the maximum length of a valid subsequence that:

• ends with value v,
• has last adjacent difference exactly d.

We also maintain:

$$best[v][d]$$

where:

$$best[v][d] = \max_{k \ge d} dp[v][k]$$

This allows us to quickly find the best subsequence ending with value v whose last difference is at least d.

Steps

1. Create two tables of size 301 x 300.

• dp[value][difference]
• best[value][difference]

All entries start at 0. 2. Maintain an array seen[value] indicating whether that value has already appeared earlier in the scan. 3. Process nums from left to right. 4. For the current number x, create a temporary array current.

current[d] will store the best subsequence ending at this specific occurrence of x with last difference d. 5. Iterate through every possible previous value pv from 1 to 300.

If pv has not appeared before, skip it. 6. Compute

$$diff = |x - pv|$$ 7. Any previous occurrence of pv can form a length-2 subsequence:

$$[pv, x]$$

so initialize the candidate length as 2. 8. We can also extend an existing subsequence ending at pv.

The decreasing-difference condition requires the previous difference to be at least diff.

By definition:

$$best[pv][diff]$$

gives exactly the longest such subsequence.

Therefore:

$$candidate = best[pv][diff] + 1$$ 9. Store the maximum candidate in current[diff]. 10. After considering all previous values, merge current into dp[x]. 11. Rebuild best[x] by scanning differences from large to small:

$$best[x][d] = \max(best[x][d+1], dp[x][d])$$ 12. Mark x as seen. 13. Track the global maximum answer.

Why it works

The state dp[v][d] stores the best valid subsequence ending with value v whose most recent difference is exactly d.

When appending a new value x, the new difference becomes |x-v|. The subsequence remains valid precisely when the previous difference is at least this new difference. The table best[v][d] stores the longest subsequence satisfying that requirement, so every valid extension is considered.

Because every transition corresponds to appending one array element while preserving order, and every valid extension is examined, the dynamic programming recurrence explores exactly all valid subsequences. Therefore the maximum length found is optimal.

Python Solution

from typing import List

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        MAX_VALUE = 300
        MAX_DIFF = 300

        dp = [[0] * MAX_DIFF for _ in range(MAX_VALUE + 1)]
        best = [[0] * MAX_DIFF for _ in range(MAX_VALUE + 1)]
        seen = [False] * (MAX_VALUE + 1)

        answer = 1

        for x in nums:
            current = [0] * MAX_DIFF

            for prev_value in range(1, MAX_VALUE + 1):
                if not seen[prev_value]:
                    continue

                diff = abs(x - prev_value)

                candidate = max(
                    2,
                    best[prev_value][diff] + 1
                )

                if candidate > current[diff]:
                    current[diff] = candidate

            for diff in range(MAX_DIFF):
                if current[diff] > dp[x][diff]:
                    dp[x][diff] = current[diff]
                    answer = max(answer, current[diff])

            best[x][MAX_DIFF - 1] = dp[x][MAX_DIFF - 1]
            for diff in range(MAX_DIFF - 2, -1, -1):
                best[x][diff] = max(
                    dp[x][diff],
                    best[x][diff + 1]
                )

            seen[x] = True

        return answer

Implementation Explanation

The dp table stores the best subsequence length for every (value, difference) pair. Since values are limited to 1..300 and differences to 0..299, the table size is fixed.

For each incoming number x, we examine every previously seen value. The new difference is determined entirely by the two values, so we compute abs(x - prev_value).

The table best allows us to instantly obtain the best subsequence ending at prev_value whose previous difference is large enough to permit the new difference. Without this suffix-maximum table, every transition would require scanning many differences.

The temporary array current ensures that states created by the current occurrence are not reused during the same iteration. Only after all transitions are computed do we merge them into dp[x].

Finally, we rebuild the suffix maxima for value x, enabling future transitions.

Go Solution

func longestSubsequence(nums []int) int {
	const MAX_VALUE = 300
	const MAX_DIFF = 300

	dp := make([][]int, MAX_VALUE+1)
	best := make([][]int, MAX_VALUE+1)

	for i := 0; i <= MAX_VALUE; i++ {
		dp[i] = make([]int, MAX_DIFF)
		best[i] = make([]int, MAX_DIFF)
	}

	seen := make([]bool, MAX_VALUE+1)
	answer := 1

	for _, x := range nums {
		current := make([]int, MAX_DIFF)

		for prevValue := 1; prevValue <= MAX_VALUE; prevValue++ {
			if !seen[prevValue] {
				continue
			}

			diff := x - prevValue
			if diff < 0 {
				diff = -diff
			}

			candidate := best[prevValue][diff] + 1
			if candidate < 2 {
				candidate = 2
			}

			if candidate > current[diff] {
				current[diff] = candidate
			}
		}

		for diff := 0; diff < MAX_DIFF; diff++ {
			if current[diff] > dp[x][diff] {
				dp[x][diff] = current[diff]
			}
			if dp[x][diff] > answer {
				answer = dp[x][diff]
			}
		}

		best[x][MAX_DIFF-1] = dp[x][MAX_DIFF-1]

		for diff := MAX_DIFF - 2; diff >= 0; diff-- {
			if dp[x][diff] > best[x][diff+1] {
				best[x][diff] = dp[x][diff]
			} else {
				best[x][diff] = best[x][diff+1]
			}
		}

		seen[x] = true
	}

	return answer
}

Go-Specific Notes

The Go implementation mirrors the Python version closely. Since all values fit comfortably inside standard integers, there is no overflow concern. Fixed-size two-dimensional slices are used for the DP tables, and absolute differences are computed manually because Go does not provide a built-in integer abs function.

Worked Examples

Example 1

Input:

nums = [16, 6, 3]

Processing 16

No previous values exist.

Value	Result
16	No transition

Current answer:

1

Processing 6

Previous value:

Previous Value	Difference	Candidate
16	10	2

Update:

dp[6][10] = 2

Current answer:

2

Processing 3

Previous values:

Previous Value	Difference	Candidate
16	13	2
6	3	best[6][3] + 1 = 3

Update:

dp[3][3] = 3

Final answer:

3

Example 2

Input:

nums = [6,5,3,4,2,1]

One optimal chain is:

6 -> 4 -> 2 -> 1

Differences:

2, 2, 1

During processing:

Transition	Difference
6 → 4	2
4 → 2	2
2 → 1	1

The sequence satisfies:

2 >= 2 >= 1

Result:

4

Example 3

Input:

nums = [10,20,10,19,10,20]

Optimal subsequence:

10 -> 20 -> 10 -> 19 -> 10

Differences:

10, 10, 9, 9

At each extension:

Previous Difference	New Difference	Valid
10	10	Yes
10	9	Yes
9	9	Yes

Length:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × 300)	For each element, iterate through all possible values 1..300 and rebuild one suffix-max row
Space	O(300 × 300)	DP and suffix-max tables

The value range is bounded by 300, which is the key reason the solution is efficient. Although n can reach 10^4, the per-element work remains constant with respect to the value domain, giving a total complexity of approximately six million operations.

Test Cases

sol = Solution()

assert sol.longestSubsequence([16, 6, 3]) == 3          # example 1
assert sol.longestSubsequence([6, 5, 3, 4, 2, 1]) == 4 # example 2
assert sol.longestSubsequence([10, 20, 10, 19, 10, 20]) == 5 # example 3

assert sol.longestSubsequence([1, 1]) == 2             # diff 0
assert sol.longestSubsequence([5, 5, 5, 5]) == 4       # all equal

assert sol.longestSubsequence([1, 300]) == 2           # minimum length array
assert sol.longestSubsequence([1, 2, 3, 4, 5]) == 5    # all diffs equal to 1

assert sol.longestSubsequence([1, 10, 2, 9, 3, 8]) >= 3 # alternating values

assert sol.longestSubsequence([100, 50, 100, 50, 100]) == 5 # repeated diff

assert sol.longestSubsequence([1, 4, 7, 10]) == 4      # diffs 3,3,3

assert sol.longestSubsequence([10, 1, 9, 2, 8, 3]) >= 4 # multiple extension choices

assert sol.longestSubsequence([300, 1, 300, 1]) == 4   # largest possible diff repeated

Test Summary

Test	Why
[16,6,3]	Official example
[6,5,3,4,2,1]	Official example
[10,20,10,19,10,20]	Official example
[1,1]	Difference zero
[5,5,5,5]	Long chain of zero differences
[1,300]	Boundary values
[1,2,3,4,5]	Constant difference sequence
[1,10,2,9,3,8]	Alternating highs and lows
[100,50,100,50,100]	Repeated large difference
[1,4,7,10]	Equal differences throughout
[10,1,9,2,8,3]	Many competing transitions
[300,1,300,1]	Maximum possible difference

Edge Cases

All Elements Are Equal

Consider:

[5, 5, 5, 5]

Every adjacent difference is 0. Since

0 >= 0 >= 0

the entire array forms a valid subsequence. Implementations that incorrectly assume differences must be positive would fail here. The DP naturally handles this because difference 0 is treated exactly like any other difference.

Maximum Difference Repeated

Consider:

[300, 1, 300, 1]

The differences are:

299, 299, 299

The sequence is valid because the differences never increase. The implementation stores states for all differences from 0 to 299, so the largest possible difference is handled without special cases.

Many Different Ways to Reach the Same State

Consider:

[10, 20, 10, 19, 10]

Several different subsequences can end at value 10 with the same last difference. A buggy implementation might keep only one predecessor. The DP instead stores the maximum length for every (value, difference) pair, ensuring that future extensions always use the strongest available state.

Length Two Subsequences

Every pair of elements automatically forms a valid subsequence because there is only one adjacent difference. The implementation explicitly allows a transition length of 2 via:

candidate = max(2, best[prev_value][diff] + 1)

This guarantees that new subsequences can always start from any previously seen value.