03-Longest-Increasing-Subsequence.md

Longest Increasing Subsequence

Problem Link

https://leetcode.com/problems/longest-increasing-subsequence/

---

Pattern

• DP
• Binary Search

---

Approach

Use patience sorting with a tails array to maintain the smallest ending value for each subsequence length.

---

Time Complexity

O(n log n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int num : nums) {
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) left = mid + 1;
                else right = mid;
            }
            tails[left] = num;
            if (left == size) size++;
        }
        return size;
    }
}