Longest Subsequence With Decreasing Adjacent Difference Python/Java solution

Implement the solution using dynamic programming where dp[i][d] stores the best subsequence ending at index i with last difference d. Iterate over all pairs (j, i), compute the absolute difference, and update the DP using a suffix maximum lookup. The same logic translates cleanly across Python, Java, C++, and Go.

What is the best approach for Longest Subsequence With Decreasing Adjacent Difference?

The best approach uses dynamic programming with a state that tracks the last adjacent difference. For each pair of indices (j, i), compute the absolute difference and extend subsequences ending at j whose previous difference is greater than or equal to the current one. Using suffix maximums over difference states reduces the complexity close to O(n^2).

Is Longest Subsequence With Decreasing Adjacent Difference asked at Google/Amazon/Meta?

Problems that combine subsequences with constrained differences appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the dynamic programming pattern of tracking a state such as the last difference is a common interview theme.

What data structure is used in Longest Subsequence With Decreasing Adjacent Difference?

The core data structure is a 2D dynamic programming table indexed by array position and difference value. Many implementations also maintain suffix maximum arrays to quickly query the best subsequence with a difference greater than or equal to a given value.

What is the time complexity of Longest Subsequence With Decreasing Adjacent Difference?

The optimized dynamic programming solution runs in O(n^2 + n·D) time, where D is the maximum possible absolute difference between values. In practice this behaves close to O(n^2). Space complexity is O(n·D) for storing subsequence lengths by index and difference.

Description Hints 2 Video 30:49

3409. Longest Subsequence With Decreasing Adjacent Difference

Q: Is Longest Subsequence With Decreasing Adjacent Difference easy or hard?

The problem is rated Medium but has a low acceptance rate because the correct DP state is not obvious. Once you recognize that the subsequence must track the previous difference and enforce a non-increasing constraint, the optimized solution follows naturally.

Q: How to solve Longest Subsequence With Decreasing Adjacent Difference in O(n^2)?

Maintain a DP table where dp[i][d] represents the longest subsequence ending at index i with last difference d. When evaluating pair (j, i), compute diff = |nums[i] − nums[j]| and extend the best subsequence at j whose last difference is ≥ diff. Using precomputed suffix maximums lets you answer this query in O(1), keeping the total around O(n^2).

Medium17.3% acceptance2 companies

You are given an array of integers nums.

Your task is to find the length of the longest subsequence seq of nums, such that the absolute differences between consecutive elements form a non-increasing sequence of integers. In other words, for a subsequence seq₀, seq₁, seq₂, ..., seq_m of nums, |seq₁ - seq₀| >= |seq₂ - seq₁| >= ... >= |seq_m - seq_{m - 1}|.

Return the length of such a subsequence.

Example 1:

Input: nums = [16,6,3]

Output: 3

Explanation:

The longest subsequence is [16, 6, 3] with the absolute adjacent differences [10, 3].

Example 2:

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

Output: 4

Explanation:

The longest subsequence is [6, 4, 2, 1] with the absolute adjacent differences [2, 2, 1].

Example 3:

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

Output: 5

Explanation:

The longest subsequence is [10, 20, 10, 19, 10] with the absolute adjacent differences [10, 10, 9, 9].

Constraints:

2 <= nums.length <= 10⁴
1 <= nums[i] <= 300

Asked at 2 companies

Juspay

Google

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Store the maximum answer for each index and every possible difference.

3409. Longest Subsequence With Decreasing Adjacent Difference

Asked at 2 companies

Topics

Hints open one at a time

Similar problems