class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        int ans=0;
        for(int i=0;i<n;i++){
            dp[i]=1;//单个字符是长度为1的严格递增子序列
            for(int j=0;j<i;j++){
               if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
               }
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
//O(n^2)
//O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

算法优化：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        //tails[k]的值代表 长度为k+1的子序列尾部元素的值
        //在遍历计算每个tails[k]，不断更新长度为 [1,k]的子序列尾部元素值，始终保持每个尾部元素值最小 （例如 [1,5,3]， 遍历到元素5 时，长度为 2的子序列尾部元素值为 5；当遍历到元素 3时，尾部元素值应更新至 3，因为 3 遇到比它大的数字的几率更大


        int[] tail=new int[n];
        int maxLen=1;
        tail[0]=nums[0];
        for(int i=1;i<n;i++){
            int num=nums[i];
            int left=0,right=maxLen-1;
            boolean flag=true;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(num>tail[mid]){
                    left=mid+1;
                }else if(num<tail[mid]){
                    flag=false;
                    right=mid-1;
                }else if(num==tail[mid]){
                    flag=false;
                    right=mid-1;
                }
            }
            //left表示小于num的元素个数
            tail[left]=num;//长度为left的递增子序列更新为以num结尾
            //flag为true说明nums[i]大于区间[0:maxLen-1]所有的tail[i]
            //此时可以将nums[i]接在tail[maxLen-1]后面 上升子序列长度+1
            //flag为false则将nums[i]插入到tail中的合适的位置j  使得tail[0...j-1]
            //因此tail数组是单调的
            if(flag){
                maxLen++;
            }
        }
        return maxLen;
    }
}
//O(nlogn)
//O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

4. 最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/

思路：

状态表示： dp[i ][j ]表示x [0..i-1 ]和y [0..j-1 ]的最长公共子序列长度

状态转移： 对两个序列中的字符xi 和yj ，可以分成以下两种情况:

• xi =yj ：求解Xi -1 和Yj -1 的最长公共子序列长度加1，dp[i ][j ]=dp[i -1][j -1]+1
  
• xi ≠yj ：可以把xi 去掉，求解Xi -1 和Yj 的最长公共子序列长度，或者把yj 去掉，求解Xi 和Yj -1 的最长公共子序列长度，取二者的最大值，dp[i ][j ]=max(dp[i ][j -1], dp[i -1][j ])
  
  边界条件： dp[i ][0]=0，dp[0][j ]=0

求解目标： dp[n -1][m-1 ]，n 、m 分别为两个字符串的长度

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m=text1.length(),n=text2.length();
        int[][] dp=new int[m+1][n+1];
        //dp[i][j]表示text1[0:i-1]  text1[0:j-1] 的LCS长度
        //当i=0时  dp[0][j]=0 表示当text1为空串时 LCS长度为0
        //当j=0时  dp[i][0]=0 表示当text2为空串时 LCS长度为0
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else if(dp[i-1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                }else{
                     dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
//O(mn)
//O(mn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5. 连续子数组的最大和

https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

状态表示： dp[i ]表示以a [i ]结尾的最大和。注意：这个最大和不是[0…i ]区间的最大连续子段和，若求解[0…n-1 ]区间的最大连续子段和，则需要从所有dp[]中求最大值。例如{-2, 1, 2, 3,-2}，dp[0]=-2，dp[1]=1，dp[2]=2，dp[3]=6，dp[4]=4，最大连续子段和为6

状态转移： 若dp[i -1]大于或等于0，则dp[i -1]累加a [i ]即可；否则dp[i ]=a [i ]; 这是因为dp[i -1]是负值时，对求解最大连续子段和没有意义

class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        int ans=nums[0];
        dp[0]=nums[0];
        for(int i=1;i<n;i++){
            dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
//O(n)
//O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15