Algorithm Day88 - Longest Increasing Subsequence

🧩 Problem Description

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

---

💬 Examples

Example 1

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101].

Example 2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3

Input: nums = [7,7,7,7,7,7,7]
Output: 1

---

💡 Approaches

1) Dynamic Programming (O(n²))

Let dp[i] be the length of the longest increasing subsequence ending at index i.
Transition: for each j < i, if nums[j] < nums[i] then dp[i] = max(dp[i], dp[j] + 1).
Answer is max(dp[i]) over all i.

2) Patience Sorting / Greedy + Binary Search (O(n log n))

Maintain an array tails[len] where tails[k] is the smallest possible tail value of an increasing subsequence with length k+1.
For each number x in nums, binary search the first index in tails with value ≥ x and replace it with x. If x is greater than all tails, append it. The length of tails is the LIS length.

This method gives O(n log n) time and O(n) space and is the recommended optimal solution for large inputs.

---

🔢 Java Code — DP (O(n²))

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

---

🔢 Java Code — Patience Sorting (O(n log n))

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int i = Collections.binarySearch(tails, x);
            if (i < 0) i = -(i + 1);
            if (i == tails.size()) tails.add(x);
            else tails.set(i, x);
        }
        return tails.size();
    }
}

Note: Collections.binarySearch returns -(insertionPoint) - 1 when the key is not found; the code above converts it into the insertion point.

---

⏱ Complexity Analysis

• DP: Time O(n²), Space O(n).
• Patience Sorting: Time O(n log n), Space O(n).

---

✍️ Summary

• Use DP for clarity or small n.
• For large inputs, use the O(n log n) approach with tails + binary search (often called patience sorting).
• The tails array stores the smallest possible tail for an increasing subsequence of each length; its size equals the LIS length.