Li Kou 300 longest increasing subsequence dynamic programming

Title Description

Give you an array of integers nums , Find the length of the longest strictly increasing subsequence .

Subsequence   Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7] It's an array [0,3,1,6,2,2,7] The subsequence .

Their thinking

• Create a new one dp Array , Initialize to 1;

• dp[ i ] It means the first one i A sequence of elements ending , The length of the largest increasing subsequence , So it's initialized to 1;

• i You need to compare the previous elements every time , If there is a ratio in front i Small elements , Need to put dp[ i ] to update , Update the equation to （ State transition equation ）：

dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)

•   New variable max To hold dp Maximum value of array , Finally back to max that will do .

Below is the picture of the boss ：

---

---

---

---

---

---

---

---

---

I / O example

Code

// Dynamic programming 

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