题解 | #最长上升子序列(一)#

import java.util.*;

//子数组必须连续，子序列不用连续。
public class Solution {
    
    //dp[i] 表示以i位置元素结尾的最长上升子序列长度
    //两种情况：1.单独i位置为一个子序列
    //2.跟在前面某个子序列（最长）后面构成子序列
    public int LIS (int[] arr) {
        // write code here

        
        //1.创建dp表
        int n = arr.length;
        if(n==0) return 0;
        int[] dp = new int[n];
        //2.初始化为1
        
        for(int i=0;i<n;i++){
            dp[i] = 1;
        }
        int ret = 1;
        //3.填表
        for(int i=1;i<n;i++){
            //此时就要寻找前面所有位置结尾中子序列最长的
            //然后与当前结合
            for(int j=0;j<i;j++){ //遍历前面所有的子序列，取最长
                //保证前面选的子序列结尾元素小于i位置
                if(arr[j] <arr[i]){

                    dp[i] = Math.max(dp[j]+1,dp[i]);

                }

            }
            ret = Math.max(ret,dp[i]);
        }

        return ret;
    }
}