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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
  /**
  dp[i]:以i结尾的最长上升子序列
  状态转移： 看i之前的元素，看是否可以拼接
  初始值：全填1
  **/
    public int LIS (int[] arr) {
        // write code here
        int n= arr.length;
        if(n==0)return 0;
        int[] dp=new int[n+1]; //以i结尾的最长上升子序列
        Arrays.fill(dp,1);
        int m=1;
        for(int i=2;i<=n;i++){
           for(int j=0;j<i-1;j++){
             if(arr[i-1]>arr[j]){
                dp[i]=Math.max(dp[i],dp[j+1]+1);
                if(dp[i]>m){
                    m=dp[i]; //记录最大值
                }
             }
           }
        }
        return m;
    }
}