Problem Summary

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

A subsequence does not need to be contiguous, but must keep the original order.

Example
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: A possible LIS is [2, 3, 7, 18].

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

Constraints

• 1 ≤ nums.length ≤ 2500
• Values may be negative or positive
• Expected time: O(n log n) or O(n²)

---

Approach 1: Dynamic Programming (O(n²)) — Simple and Clear

Key Idea

For each element, compute the LIS ending at that element.

Define:

dp[i] = length of the longest increasing subsequence ending at index i

To compute dp[i], check all previous elements:

if nums[j] < nums[i],
    dp[i] = max(dp[i], dp[j] + 1)

Why This Works

Every LIS ending at i must extend one LIS ending at some earlier position j where nums[j] < nums[i].

We try all possibilities and pick the best.

Steps

1. Initialize all dp[i] = 1 (each element is an LIS of length 1).
2. For each i from 1 to n-1:
   • Check all j < i.
   • Update dp[i] accordingly.
3. Track the maximum value in dp.

Time Complexity

O(n²), acceptable for n ≤ 2500.

---

Java Code (O(n²) DP)

class Solution {
    public int lengthOfLIS(int[] nums) {

        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;  // every element alone is LIS of length 1
            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;
    }
}

---

Approach 2: Binary Search (O(n log n)) — Optimal Solution

This is the classic optimal LIS algorithm.

Key Idea

Maintain an array tails[] where:

tails[length] = the smallest possible ending value of an increasing subsequence of given length

For each number:

• Use binary search on tails to find where it fits:
  • Replace an element in tails
  • Or extend tails

t length of tails = LIS length

Why This Works

The tails array does not store a real subsequence, but stores optimal endpoints that allow future extension.

It ensures:

• Smallest possible tail for subsequences of different lengths
• Greedy replacement + binary search yields O(n log n)

Steps

For each number x:

1. Binary search tails to find the first element ≥ x.
2. If none found, append x to tails.
3. Otherwise replace that element with x.

Length of tails = LIS length.

---

Java Code (O(n log n) Binary Search)

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {

        int[] tails = new int[nums.length];
        int size = 0;

        for (int x : nums) {
            int left = 0, right = size;

            // find the first index where tails[index] >= x
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < x) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = x;
            if (left == size) size++;
        }

        return size;
    }
}

---

Dry Run (Binary Search Approach)

Input:
nums = [10, 9, 2, 5, 3, 7, 101, 18]

Let tails = [] initially.

1. Insert 10 → tails = [10]
2. Insert 9 → replace 10 → [9]
3. Insert 2 → replace 9 → [2]
4. Insert 5 → append → [2, 5]
5. Insert 3 → replace 5 → [2, 3]
6. Insert 7 → append → [2, 3, 7]
7. Insert 101 → append → [2, 3, 7, 101]
8. Insert 18 → replace 101 → [2, 3, 7, 18]

Final tails array = [2, 3, 7, 18]
Length = 4 → LIS length = 4

---

Complexity Analysis

Approach 1 (DP):
Time O(n²), Space O(n)

Approach 2 (Binary Search):
Time O(n log n), Space O(n)

Binary search approach is preferred for large inputs.

---

Edge Cases

• Single element → LIS = 1
• All numbers equal → LIS = 1
• Strictly increasing → LIS = n
• Strictly decreasing → LIS = 1
• Mixed positive and negative values → handled naturally