300. Longest Increasing Subsequence

Question

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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.

Thinking:

• Method:
  • DP

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length + 1];
        int res = 1;
        for(int i = 1; i <= nums.length; i++){
            dp[i] = 1;
            int cmp = nums[i - 1];
            for(int j = 0; j < i - 1; j++){
                if(nums[j] < cmp){
                    dp[i] = Math.max(dp[i], dp[j + 1] + 1);
                }
                res = Math.max(dp[i], res);
            }
        }
        return res;
    }
}

Second time

1. Still use dp to solve this question. O(N^2)

   class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int[] dp = new int[len + 1];
        for(int i = 1; i <= len; i++) dp[i] = 1;
        int result = 1;
        for(int i = 2; i <= len; i++){
            int num = nums[i - 1];
            for(int j = i - 1; j >= 1; j--){
                if(num > nums[j - 1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(dp[i], result);
        }
        return result;
    }
   }