LeetCode刷题-动态规划- Longest Increasing Subsequence

题目:
给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(_n2_) 。

进阶:你能将算法的时间复杂度降低到 O(_n_log_n_) 吗?


思路:构建一个数组dp[i]用于存放到相应位置时最长的上升子序列长度,那么需要比较脚标i前面的所有比nums[i]小的数的dp值,找到其中最大的dp值然后加1。
dp[i]=Math.max(dp[j]+1,dp[i])


public static int lengthOfLIS(int[] nums) {

    //数组为空时返回0
    if(nums.length==0||nums==null){
        return 0;
    }
int[]dp=new int[nums.length];//新建数组dp,用于放nums对应角标处最长上升数组dp的长度
    int max=1;//若整个数组都降序,则max为1;
for (int i=0;i<nums.length;i++){
    dp[i]=1;//先填充最小值1
    //找出nums[i]前面所有数中比nums[i]小的数
    for (int j=0;j<i;j++){
        if (nums[i]>nums[j]){
            //将dp[j]+1与原dp[i]最大值赋给新dp[i]
            dp[i]=Math.max(dp[j]+1,dp[i]);
        }
    }
    max=Math.max(max,dp[i]);//不断更新最长的上升数组长度
}
return max;
}

评论

暂无评论