讨论/《中级算法》 - 最长上升子序列/
《中级算法》 - 最长上升子序列
/*
根据官方题解,这里动态转移方程是:
    dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
官方意思就是  (以示例2为例)
    用一个dp数组保存 以nums数组当前索引位置的元素为末尾的最长的递增子序列的长度
    dp[0] = 1  //一个数就是一个子序列的长度1  最长子序列:[0]
    dp[1] = max(dp[0]+1 = 2, 前面所有元素中比当前元素的小的最大dp值  [0,1]
    dp[2] = max(没有==0)+1 = 1,没有比0小的,所以直接是1     [0]
    dp[3] = max(dp[0],dp[1],d[2])+1 = 3,通过nums数组得有0,1,2位置的元素小于当前,找最大子序列长度来+1  [0,1,3]
    dp[4] = max(dp[0],dp[1],dp[2])+1 = 3 ......  [0,1,2]
    dp[5] = max(dp[0],dp[1],dp[2],dp[4])+1 = 4  ......  [0,1,2,3]

    所以得到dp数组为[1,2,1,3,3,4]
    依次对应着nums数组索引位置元素为末尾的最长递增子序列的长度
    然后找到其中最大值即可。
*/
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = 1;
        int res = 1;
        for(int i = 1;i<len;i++){
            int max = Integer.MIN_VALUE;
            for(int j = 0;j<i;j++){
                if(nums[j]<nums[i] && dp[j]>max){
                    max = dp[j];
                }
            }
            dp[i] = max == Integer.MIN_VALUE ? 1 : max+1;
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
展开全部 6 讨论