Longest Increasing Subsequence (Longest Strictly Rising Pick)

• Longest Increasing Subsequence (LIS) – longest strictly increasing selection preserving original order.
• Quadratic DP – dp[i] = max(dp[j] + 1) for all j < i where a[j] < a[i], in O(n^2).
• Patience sorting – maintain a tails array of smallest ending values per length; binary-search placement.
• Answer – max over dp[] (quadratic) or tails.size() (patience sorting).
• Reconstruction – predecessor pointers needed to recover the actual subsequence.
• Variant – for non-decreasing, use upper_bound instead of lower_bound.

What is the Longest Increasing Subsequence?

The LIS of an array is the longest subsequence whose values are strictly increasing while keeping the original order. Elements do not need to be contiguous. For [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 18] with length 4.

package com.bank.dsa;

public class LisDP {

    public static int lis(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        java.util.Arrays.fill(dp, 1);
        int best = 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }
}

4

How does the quadratic DP work?

For each index i, dp[i] is the length of the longest increasing subsequence ending exactly at index i. Every element alone is a subsequence of length 1, so we initialise dp[i] = 1. Then for each i, we look back at every j < i. If a[j] < a[i], the subsequence ending at j can be extended by a[i], so dp[i] = max(dp[i], dp[j] + 1).

The answer is the maximum dp[i] over all indices, not dp[n-1], because the LIS can end at any position.

How does the O(n log n) patience sorting work?

Maintain a tails array where tails[k] holds the smallest possible ending value of an increasing subsequence of length k + 1. For each element x, binary-search for the leftmost position in tails where the value is >= x. If no such position exists, append x (extending the longest known subsequence). Otherwise, replace that position with x.

package com.bank.dsa;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LisPatienceSorting {

    public static int lis(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int pos = Collections.binarySearch(tails, x);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) tails.add(x);
            else tails.set(pos, x);
        }
        return tails.size();
    }

    public static void main(String[] args) {
        System.out.println(lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }
}

4

How is the quadratic different from patience sorting?

| Aspect | Quadratic DP | Patience sorting |
|---|---|---|
| Time | O(n^2) | O(n log n) |
| Space | O(n) | O(n) |
| Gets actual LIS | With predecessor pointers | Tails is NOT a valid LIS |
| Code complexity | Simple loops | Binary search needed |
| Best for | Small n or reconstruction | Large n, length only |

Why is the tails array not a valid subsequence?

The tails array stores the smallest possible ending value for each length. As new elements are processed, earlier positions in tails get overwritten with smaller values. These overwrites can mix elements from different subsequences. The length of tails is always correct, but the contents may not form a valid subsequence.

To reconstruct the actual LIS, maintain predecessor pointers: for each element processed, record which element precedes it in the best subsequence.

package com.bank.dsa;

import java.util.*;

public class LisReconstruct {

    public static List<Integer> findLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return Collections.emptyList();

        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        int bestIdx = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            if (dp[i] > dp[bestIdx]) bestIdx = i;
        }

        List<Integer> result = new ArrayList<>();
        for (int i = bestIdx; i != -1; i = parent[i]) result.add(nums[i]);
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }
}

[2, 3, 7, 18]

What are common mistakes?

Returning dp[n-1] instead of max(dp) is the most common mistake. The LIS does not have to end at the last element.

// WRONG
return dp[n - 1];

// CORRECT
int best = 0;
for (int x : dp) best = Math.max(best, x);
return best;

Using <= instead of < gives longest non-decreasing subsequence, not strictly increasing.

What are the edge cases?

Empty array returns 0. Single element returns 1. Strictly increasing array returns its length. Strictly decreasing array returns 1.

package com.bank.dsa;

public class LisEdge {
    public static void main(String[] args) {
        System.out.println(LisDP.lis(new int[]{}));          // 0
        System.out.println(LisDP.lis(new int[]{5}));         // 1
        System.out.println(LisDP.lis(new int[]{1,2,3,4}));   // 4
        System.out.println(LisDP.lis(new int[]{4,3,2,1}));   // 1
    }
}

0
1
4
1

When should you use LIS in banking?

At the National Bank of India, the credit-scoring team analyses a customer's monthly closing balances to find the longest stretch of strictly rising months. A long rising streak is a strong positive signal in the financial health score.

package com.bank.service;

public class CreditHealthAnalyser {

    public static int longestRisingStreak(int[] balances) {
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        for (int b : balances) {
            int pos = java.util.Collections.binarySearch(tails, b);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) tails.add(b);
            else tails.set(pos, b);
        }
        return tails.size();
    }

    public static void main(String[] args) {
        int[] balances = {45000, 42000, 48000, 50000, 47000, 55000, 60000, 58000};
        System.out.println("Longest rising streak: " + longestRisingStreak(balances) + " months");
    }
}

Longest rising streak: 5 months

What should a senior engineer know?

The patience sorting name comes from the card game solitaire (patience). The number of piles formed equals the LIS length, a consequence of Dilworth's theorem.

For the non-strictly increasing variant, change the binary search comparison. In Java, Collections.binarySearch finds exact matches; for upper_bound behaviour, search for x + 1 or use a custom comparator.

LIS can also be solved by reducing to LCS: sort the array, then find the LCS between the original and sorted arrays. This gives O(n^2) time and is useful for understanding but offers no speed advantage.