leetcode300-最长上升子序列

原题

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

示例:

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

说明:

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

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

解法

思想

动态规划,对于某个元素,其dp值应该等于左边比其小的元素中最大的dp值+1。

代码

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxCount = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) maxval = Math.max(maxval, dp[j]);
            }
            dp[i] = maxval + 1;
            maxCount = Math.max(maxCount, dp[i]);
        }
        return maxCount;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode300-%e6%9c%80%e9%95%bf%e4%b8%8a%e5%8d%87%e5%ad%90%e5%ba%8f%e5%88%97/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月13日 22:54
下一篇 2020年3月14日 19:37

相关推荐

  • 拉帮结派的数据结构-并查集

    本文参考资源: 超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客 概述 并查集通常用作集合的合并。 并查集是一种树形结构,又叫“不相交集合”,保持了一组不…

    2020年2月17日
    0140
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0640
  • leetcode23-合并K个排序链表

    原题 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->…

    算法 2020年2月4日
    0170
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0120
  • leetcode217-存在重复元素

    原题 给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。 示例1: 输入: [1,2,3…

    算法 2019年12月18日
    070
  • leetcode134-加油站

    原题 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[…

    算法 2020年2月16日
    080
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 5天前
    030
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    070
  • leetcode209-长度最小的子数组

    原题 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = …

    算法 2019年11月20日
    0160
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    090

发表回复

登录后才能评论