Day 18 of leetcode dynamic planning introduction

300. The longest increasing subsequence

376. Swing sequence

---

300. The longest increasing subsequence

Realize the idea ：

I use this question O(n^2) Time complexity of completed , It's traversal , It's simple .

Implementation code ：

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

But then I read the standard solution , Use dichotomy to solve , Feel more clever . The solution is in the link below .

Power button

  Code attached ：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tail=new int[nums.length];
        int ans=0;
        for(int num:nums){
            int i=0,j=ans;
            while(i<j){
                int m=(i+j)/2;
                if(tail[m]<num) i=m+1;
                else j=m;
            }
            tail[i]=num;
            if(ans==j) ans++;
        }
        return ans;
    }
}

---

376. Swing sequence

Realize the idea ：

  A very simple state transition equation .

Implementation code ：

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n=nums.length;
        int[] up=new int[n];
        int[] down=new int[n];
        up[0]=1;
        down[0]=1;
        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){
                up[i]=Math.max(up[i-1],down[i-1]+1);
                down[i]=down[i-1];
            }else if(nums[i]<nums[i-1]){
                up[i]=up[i-1];
                down[i]=Math.max(up[i-1]+1,down[i-1]);
            }else{
                up[i]=up[i-1];
                down[i]=down[i-1];
            }
        }
        return Math.max(up[n-1],down[n-1]);
    }
}