Approach

Longest Increasing Subsequence

Problem Statement

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

A subsequence is an array that can be derived from another 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], length = 4.

Example 2:

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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1
Explanation: All elements are the same, so LIS is just one element.

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Approach

Key Insight

For each position i, find the longest increasing subsequence ending at i.

We check all previous elements j < i:

If nums[j] < nums[i], we can extend that subsequence
dp[i] = max(dp[j] + 1) for all valid j

Solution 1: Dynamic Programming O(n²)

Build DP table tracking LIS length ending at each index.

Algorithm:

Create DP array, initialize all to 1 (each element is LIS of length 1)
For each i from 1 to n:
- For each j from 0 to i-1:
  - If nums[j] < nums[i]:
    - dp[i] = max(dp[i], dp[j] + 1)
Return max(dp)

Solution 2: Binary Search + DP O(n log n)

Maintain array of smallest tail elements.

Algorithm:

Create tails array
For each number:
- Binary search for position in tails
- Replace or append to maintain increasing sequence
Return length of tails

Visualization Example

For nums = [10, 9, 2, 5, 3, 7]:

Index:  0   1  2  3  4  5
nums:  10   9  2  5  3  7
dp:     1   1  1  2  2  3

LIS ending at each index:
dp[0] = 1  → [10]
dp[1] = 1  → [9]
dp[2] = 1  → [2]
dp[3] = 2  → [2, 5]
dp[4] = 2  → [2, 3]
dp[5] = 3  → [2, 3, 7] or [2, 5, 7]

Maximum LIS length = 3

Complexity Analysis

DP Solution O(n²):

Time Complexity: O(n²) - nested loops
Space Complexity: O(n) - DP array

Binary Search Solution O(n log n):

Time Complexity: O(n log n) - binary search for each element
Space Complexity: O(n) - tails array

Pattern Recognition

This problem demonstrates:

Dynamic Programming with subsequence tracking
Optimal substructure property
Binary search optimization technique
Patience sorting algorithm
Foundation for many LIS variants (LCS, Russian Doll Envelopes)

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Dynamic Programming O(n²)
5    public int lengthOfLIS(int[] nums) {
6        if (nums == null || nums.length == 0) return 0;
7
8        int n = nums.length;
9        // dp[i] = length of LIS ending at index i
10        int[] dp = new int[n];
11        Arrays.fill(dp, 1);
12
13        int maxLength = 1;
14
15        // For each position
16        for (int i = 1; i < n; i++) {
17            // Check all previous positions
18            for (int j = 0; j < i; j++) {
19                // If can extend subsequence from j to i
20                if (nums[j] < nums[i]) {
21                    dp[i] = Math.max(dp[i], dp[j] + 1);
22                }
23            }
24            maxLength = Math.max(maxLength, dp[i]);
25        }
26
27        return maxLength;
28    }
29
30    // Solution 2: Binary Search + DP O(n log n)
31    public int lengthOfLISOptimized(int[] nums) {
32        // tails[i] = smallest tail element of LIS with length i+1
33        List<Integer> tails = new ArrayList<>();
34
35        for (int num : nums) {
36            // Binary search for position to insert/replace
37            int pos = binarySearch(tails, num);
38
39            // Replace or append
40            if (pos == tails.size()) {
41                tails.add(num);
42            } else {
43                tails.set(pos, num);
44            }
45        }
46
47        return tails.size();
48    }
49
50    private int binarySearch(List<Integer> tails, int target) {
51        int left = 0, right = tails.size();
52
53        while (left < right) {
54            int mid = left + (right - left) / 2;
55            if (tails.get(mid) < target) {
56                left = mid + 1;
57            } else {
58                right = mid;
59            }
60        }
61
62        return left;
63    }
64
65    // Solution 3: DP with Reconstruction
66    public List<Integer> findLIS(int[] nums) {
67        if (nums == null || nums.length == 0) {
68            return new ArrayList<>();
69        }
70
71        int n = nums.length;
72        int[] dp = new int[n];
73        int[] prev = new int[n];
74        Arrays.fill(dp, 1);
75        Arrays.fill(prev, -1);
76
77        int maxLength = 1;
78        int maxIdx = 0;
79
80        // Build DP table with backtracking info
81        for (int i = 1; i < n; i++) {
82            for (int j = 0; j < i; j++) {
83                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
84                    dp[i] = dp[j] + 1;
85                    prev[i] = j;
86                }
87            }
88            if (dp[i] > maxLength) {
89                maxLength = dp[i];
90                maxIdx = i;
91            }
92        }
93
94        // Reconstruct LIS
95        List<Integer> lis = new ArrayList<>();
96        int idx = maxIdx;
97        while (idx != -1) {
98            lis.add(nums[idx]);
99            idx = prev[idx];
100        }
101
102        Collections.reverse(lis);
103        return lis;
104    }
105}
106