专栏首页机器学习入门674. Longest Continuous Increasing Subsequence

674. Longest Continuous Increasing Subsequence

LWC 49:674. Longest Continuous Increasing Subsequence

Problem:

Given an unsorted array of integers, find the length of longest continuous increasing subsequence.

Example 1:

Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.

Example 2:

Input: [2,2,2,2,2] Output: 1 Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note:

Length of the array will not exceed 10,000.

思路: 用了DP记录当前序列的最大连续长度。

dp[i] 表示当前位置的最大连续长度

更新:
dp[i] = dp[i - 1] + 1 if (前一元素小于当前元素)

代码如下:

    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

此题不一定需要DP,直接用单个变量控制即可。

代码如下:

    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int max = 1;
        for (int i = 1, k = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                k ++;
                max = Math.max(max, k);
            }
            else {
                k = 1;
            }
        }
        return max;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LWC 54:698. Partition to K Equal Sum Subsets

    LWC 54:698. Partition to K Equal Sum Subsets 传送门:698. Partition to K Equal Sum S...

    用户1147447
  • LWC 56:718. Maximum Length of Repeated Subarray

    LWC 56:718. Maximum Length of Repeated Subarray 传送门:718. Maximum Length of Repea...

    用户1147447
  • 剑指Offer LeetCode 面试题21. 调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    TrueDei
  • LeetCode第七天

    ==数组 Medium== 40.(162)Find Peak Element ? JAVA //斜率思想,二分法 class Solution { p...

    郭耀华
  • LeetCode 1262. 可被三整除的最大和(DP)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/greatest-sum-divisible-by-t...

    Michael阿明
  • 最长重复子数组

    ​ 模板题直接上dp,dp[i] [j] 为A数组以 i 结尾,B数组以 j 结尾的最长公共子串长度。

    你的益达
  • LWC 56:718. Maximum Length of Repeated Subarray

    LWC 56:718. Maximum Length of Repeated Subarray 传送门:718. Maximum Length of Repea...

    用户1147447
  • LintCode 最长上升子序列题目分析代码

    说明 最长上升子序列的定义: 最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列,这种子序列不一定是连续的或者唯一的。http...

    desperate633
  • leetcode410. Split Array Largest Sum

    将一个长度为n的正整数数组分割为m个非空的连续子数组,并分别计算每个子数组中所有元素的和。求一种分割方式,使得该分割方式生成的最大子数组和为所有分割方式中最小的...

    眯眯眼的猫头鹰

扫码关注云+社区

领取腾讯云代金券