Longest Increasing Subsequence — Practice

Problem

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

Examples

Example 1

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

Output: 4

Explanation: [2,3,7,101]

Example 2

Input: nums = [0,1,0,3,2,3]

Output: 4

Explanation: [0,1,2,3]

Constraints

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

Hints

Hint 1

The direct O(n^2) DP: dp[i] = length of the longest increasing subsequence ENDING at index i, built by checking every earlier index j.

Hint 2

dp[i] = 1 + max(dp[j]) for every j < i where nums[j] < nums[i] — or just 1 if no such j exists.

Hint 3

The O(n log n) improvement replaces the O(n) inner scan with binary search, by maintaining a different kind of state: not 'best ending here,' but 'smallest possible tail for each achievable length.'

Solutions

public int lengthOfLISDP(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // every element is a subsequence of length 1 on its own
    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;
}

Time: O(n^2) · Space: O(n)