Longest Increasing Subsequence

Problem Statement

Given an array of integers, find the length of the longest strictly increasing subsequence. A subsequence doesn't need to be contiguous but must maintain relative order.

Example:

• Input: arr = [10, 9, 2, 5, 3, 7, 101, 18]
• Output: 4 (LIS is [2, 3, 7, 101] or [2, 5, 7, 101])

Noob-Friendly Explanation

Imagine you're watching stock prices over several days: 10, 9, 2, 5, 3, 7, 101, 18. You want to find the longest streak of increasing prices, but you're allowed to skip some days. So 2 → 5 → 7 → 101 is a valid increasing sequence of length 4 (you skipped 10, 9, 3, and 18). The key is: each number must be bigger than the one before it in your chosen sequence.

Approach 1: Brute Force (Recursion)

Intuition

For each element, decide whether to include it in the subsequence or skip it. Include it only if it's larger than the previous element chosen.

Algorithm

1. Maintain the index of the last included element
2. For the current element, if it's greater than the last included, try including it
3. Also try skipping it
4. Return the maximum

public class Solution {
    public int lis(int[] arr, int n, int prev, int curr) {
        if (curr == n) return 0;

        // Skip current element
        int skip = lis(arr, n, prev, curr + 1);

        // Include current element if it's greater than previous
        int include = 0;
        if (prev == -1 || arr[curr] > arr[prev]) {
            include = 1 + lis(arr, n, curr, curr + 1);
        }

        return Math.max(skip, include);
    }

    public int lengthOfLIS(int[] arr) {
        return lis(arr, arr.length, -1, 0);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Each element has 2 choices (include or skip)
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Binary Search with Patience Sorting)

Intuition

Maintain a list of the smallest possible tail elements for increasing subsequences of various lengths. For each new element, use binary search to find where it fits. This doesn't give the actual LIS but gives the correct length.

Algorithm

1. Create an empty list tails
2. For each element in the array:
   • Binary search for the position where it should go in tails
   • If it's larger than all elements, append it (extends LIS)
   • Otherwise, replace the element at the found position (keeps tails as small as possible)
3. The length of tails is the LIS length

public class Solution {
    public int lengthOfLIS(int[] arr) {
        int n = arr.length;
        int[] tails = new int[n];
        int size = 0;

        for (int num : arr) {
            int lo = 0, hi = size;

            // Binary search for the position
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails[mid] < num) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }

            tails[lo] = num;

            // If num is larger than all tails, extend the size
            if (lo == size) {
                size++;
            }
        }

        return size;
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - For each of n elements, binary search takes O(log n)
• Space Complexity: O(n) - The tails array