Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1

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

Example 2

Input: nums = [0, 1, 0, 3, 2, 3] Output: 4 Explanation: The longest increasing subsequence is [0, 1, 2, 3], which has length 4.

Solution Approach - DP O(n²)

We maintain a dp array where dp[i] represents the length of the longest increasing subsequence ending at index i. For each element, we look back at all previous elements and if a smaller element is found, we can extend that subsequence.

Initialize every dp[i] = 1 (every element alone is a subsequence of length 1).
For each index i, iterate over all indices j < i. If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).
The answer is the maximum value in the dp array.

Java

public class LongestIncreasingSubsequence {

    // O(n^2) DP approach
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    // O(n log n) Patience sort approach using binary search
    public int lengthOfLISOptimal(int[] nums) {
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        for (int num : nums) {
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) < num) lo = mid + 1;
                else hi = mid;
            }
            if (lo == tails.size()) tails.add(num);
            else tails.set(lo, num);
        }
        return tails.size();
    }
}

Complexity Analysis:

Time complexity: O(n²) for DP approach; O(n log n) for patience sort approach.
Space complexity: O(n) for the dp / tails array.