Longest Subsequence With Decreasing Adjacent Difference

Longest Subsequence With Decreasing Adjacent Difference - Problem

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ₘ of nums, we need:

|seq₁ - seq₀| ≥ |seq₂ - seq₁| ≥ ... ≥ |seqₘ - seqₘ₋₁|

Return the length of such a subsequence.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,7,2,8]

› Output: 3

💡 Note: One valid subsequence is [4,7,2] with differences [3,5]. Since 3 ≤ 5 is false, we need [7,4,2] with differences [3,2] where 3 ≥ 2 ✓. Actually, [4,2,8] gives differences [2,6] which is invalid. The longest valid is [7,2] with length 2, but [4,7,2,8] checking all: [4,7] diff=3, [7,2,8] diffs=[5,6] invalid. Best is [4,7,8] with diffs=[3,1] where 3≥1 ✓, giving length 3.

Example 2 — Decreasing Differences

$ Input: nums = [10,5,3,2]

› Output: 4

💡 Note: The subsequence [10,5,3,2] has differences [5,2,1]. Since 5 ≥ 2 ≥ 1, this forms a valid non-increasing sequence of differences. The entire array can be used, giving length 4.

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: A single element forms a valid subsequence of length 1 (no differences to check).

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers [4,7,2,8]

Process

Output

Length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Use dynamic programming to track subsequences by their last two elements and extend only when differences decrease

Asked in

G Google 15 f Meta 12 a Amazon 8

This problem requires finding the longest subsequence where absolute differences between consecutive elements form a non-increasing sequence. The key insight is to use dynamic programming with states tracking the last two elements of each subsequence. The optimal approach uses DP with HashMap for efficient state management. Time: O(n³), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - 2D State	O(n³)	O(n²)	Use DP with states (index, last_element, last_difference)
Optimized DP with HashMap	O(n³)	O(n²)	Efficient DP using HashMap to track states with pruning
Brute Force - Generate All Subsequences	O(2ⁿ × n)	O(n)	Generate all possible subsequences and check the difference condition

Dynamic Programming - 2D State — Algorithm Steps

Step 1: For each element, try it as start of a new subsequence
Step 2: For each pair of elements, calculate their difference
Step 3: Extend existing subsequences if new difference ≤ last difference
Step 4: Track maximum length across all states

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with each pair as base case

Extend

Add elements if difference condition holds

Optimize

Track best length for each state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int abs_diff(int a, int b) {
    return a > b ? a - b : b - a;
}

int solution(int* nums, int numsSize) {
    if (numsSize <= 2) return numsSize;
    
    // Use 2D array for dp[i][j]
    int dp[1000][1000];
    memset(dp, 0, sizeof(dp));
    int maxLength = 2;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            // Try nums[j] as second-to-last, nums[i] as last
            int currentDiff = abs_diff(nums[i], nums[j]);
            int bestLen = 2; // At least these two elements
            
            // Look for valid previous subsequences ending at j
            for (int k = 0; k < j; k++) {
                if (dp[j][k] > 0) {
                    int prevDiff = abs_diff(nums[j], nums[k]);
                    if (prevDiff >= currentDiff) {
                        if (dp[j][k] + 1 > bestLen) {
                            bestLen = dp[j][k] + 1;
                        }
                    }
                }
            }
            
            dp[i][j] = bestLen;
            if (bestLen > maxLength) {
                maxLength = bestLen;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: for each element, try all previous elements as second-to-last

⚠ Quadratic Growth

Space Complexity

O(n²)

DP table storing best length for each (last_element, second_last_element) pair

⚠ Quadratic Space

30.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - 2D State — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler