写点什么

【LeetCode】最长递增子序列 Java 题解

用户头像
HQ数字卡
关注
发布于: 57 分钟前

题目描述

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。


子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。


示例 1:
输入:nums = [10,9,2,5,3,7,101,18]输出:4解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路总结

  • 今天的算法题目,需要找到最长严格递增子序列的长度。

  • 采用动态规划的方式解题:dp[i] 的值代表 nums 前 i 个数字的最长子序列长度。初始值 dp[i] 为 1。

  • 然后每次遍历 0 到 i - 1 区间,与 nums[i]比较大小 ,动态更新 dp[i] 的最值。代码如下:

通过代码

class Solution {    public int lengthOfLIS(int[] nums) {        int n = nums.length;        int ans = 0;        if (n == 0) {            return ans;        }
int[] dp = new int[n]; dp[0] = 1; ans = 1; for (int i = 1; i < n; i++) { dp[i] = 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 * n), 空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 57 分钟前阅读数: 3
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】最长递增子序列Java题解