300. Longest Increasing Subsequence

Published on February 4, 2024

Question

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

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Approach

Use dp, define dp[i] as the ith element, that so far it can be longest subsequence.
1. The status transform equation is if the element nums[i] is larger than the previous element nums[j], then dp[i] = Math.max(dp[j] + 1, dp[i]);

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        for (int num : dp) {
            res = Math.max(res, num);
        }
        return res;
    }
}

Follow up

Use O(nlogn) time complexity algorithm.

Algorithm2

The idea is basically to maintain a list, each time there is a large element, append it, otherwise replace a element with a smaller on, so that the whole array become "smaller", and can be longer. Because it's smaller, it can contain more large number.

Code2

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > list.get(list.size() - 1)) {
                list.add(nums[i]);
            } else {
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j) >= nums[i]) {
                        list.set(j, nums[i]);
                        break;
                    }
                }
            }
        }
        return list.size();
    }
}

But we are required with O(nlogn), so binary search will be leveraged in search the first small element in the else condition.

class Solution {
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> sub = new ArrayList<>();
        sub.add(nums[0]);
        
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num > sub.get(sub.size() - 1)) {
                sub.add(num);
            } else {
                int j = binarySearch(sub, num);
                sub.set(j, num);
            }
        }
        
        return sub.size();
    }
    
    private int binarySearch(ArrayList<Integer> sub, int num) {
        int left = 0;
        int right = sub.size() - 1;
        int mid = (left + right) / 2;
        
        while (left < right) {
            mid = (left + right) / 2;
            if (sub.get(mid) == num) {
                return mid;
            }
            
            if (sub.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}