Longest Increasing Subset – From Last

Find the longest strictly increasing subsequence starting from the end of the array, with ties broken by first occurrence

Understand the Problem

Problem Statement

Given N numbers, the program must print the longest increasing subset from the end. If multiple subsets are present with the same longest length, print the first occurring subset.

Constraints

2 ≤ N ≤ 9999
Each number value is between -99999 and 99999
The subset must be strictly increasing (no equal consecutive elements)
The subset must appear from the end of the original array

Examples

Example 1

Input

8
2 18 18 11 6 17 11 4

Output

4 11 17

Explanation

There are two subsets of length 3 from the end: 4 11 17 and 6 11 18. Since 4 11 17 appears first when scanning from the end, it is selected and printed.

Example 2

Input

5
1 2 3 4 5

Output

1 2 3 4 5

Explanation

The entire array is increasing, so the longest increasing subset from the end is the whole array in reverse order (5 4 3 2 1), but since we need the subset from the end, we take 1 2 3 4 5.

Solution

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

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Reverse array to work from end
    int rev[n];
    for(int i = 0; i < n; i++) {
        rev[i] = arr[n-1-i];
    }
    
    // DP array to store LIS length ending at each position
    int dp[n];
    int prev[n];
    
    // Initialize
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        prev[i] = -1;
    }
    
    int maxLength = 1;
    int bestEnd = 0;
    
    // Fill DP table
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(rev[j] < rev[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        
        // Track first occurrence of maximum length
        if(dp[i] > maxLength) {
            maxLength = dp[i];
            bestEnd = i;
        }
    }
    
    // Reconstruct the subsequence
    int result[maxLength];
    int idx = bestEnd;
    int pos = maxLength - 1;
    
    while(idx != -1) {
        result[pos] = rev[idx];
        pos--;
        idx = prev[idx];
    }
    
    // Print result
    for(int i = 0; i < maxLength; i++) {
        printf("%d ", result[i]);
    }
    
    return 0;
}

Time:O(n²) - We have nested loops where each position checks all previous positions

Space:O(n) - We use additional arrays of size n for DP and reconstruction

Approach:

The C solution:

Reads input values into an array
Reverses the array to work from the end
Uses dynamic programming with two arrays: dp[] for lengths and prev[] for reconstruction
For each position, checks all previous positions to find longer increasing sequences
Tracks the maximum length and ending position
Reconstructs the actual subsequence using the prev[] array
Prints the result

Visual Explanation

Loading diagram...

All Problems