博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LintCode] Longest Increasing Continuous Subsequence
阅读量:5838 次
发布时间:2019-06-18

本文共 2347 字,大约阅读时间需要 7 分钟。

Problem 最长连续递增/递减子序列

Give an integer array,find the longest increasing continuous subsequence in this array.

An increasing continuous subsequence:
Can be from right to left or from left to right.
Indices of the integers in the subsequence should be continuous.

Example

For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.

For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.

Note

设置正向计数器,后一位增加则计数器加1,否则置1。反向计数器亦然。

每一次比较后将较大值存入max。

Solution

O(1) space, O(n) time

public class Solution {    public int longestIncreasingContinuousSubsequence(int[] A) {        if (A == null || A.length == 0) return 0;        int n = A.length;        int count = 1, countn = 1, max = 1;        int i = 1;        while (i != n) {            if (A[i] >= A[i-1]) {                count++;                countn = 1;                max = Math.max(max, count);            }            else {                countn++;                count = 1;                max = Math.max(max, countn);            }            i++;        }        return max;    }}

DP using two dp arrays, O(n) space

public class Solution {    public int longestIncreasingContinuousSubsequence(int[] A) {        if (A == null || A.length == 0) return 0;        int n = A.length;        if (n == 1) return 1;        int[] dp = new int[n];        int[] pd = new int[n];        int maxdp = 0, maxpd = 0;        dp[0] = 1;        for (int i = 1; i < n; i++) {            dp[i] = A[i] >= A[i-1] ? dp[i-1]+1 : 1;            maxdp = Math.max(maxdp, dp[i]);        }        pd[n-1] = 1;        for (int i = n-2; i >= 0; i--) {            pd[i] = A[i] >= A[i+1] ? pd[i+1]+1 : 1;            maxpd = Math.max(maxpd, pd[i]);        }        return Math.max(maxdp, maxpd);    }}

DP using one dp arrays, O(n) space

public class Solution {    public int longestIncreasingContinuousSubsequence(int[] A) {        if (A == null || A.length == 0) return 0;        int n = A.length;        if (n == 1) return 1;        int[] dp = new int[n];        int maxdp = 0, maxpd = 0;        dp[0] = 1;        for (int i = 1; i < n; i++) {            dp[i] = A[i] >= A[i-1] ? dp[i-1]+1 : 1;            maxdp = Math.max(maxdp, dp[i]);        }        for (int i = 1; i < n; i++) {            dp[i] = A[i] <= A[i-1] ? dp[i-1]+1 : 1;            maxpd = Math.max(maxpd, dp[i]);        }        return Math.max(maxdp, maxpd);    }}

转载地址:http://ikncx.baihongyu.com/

你可能感兴趣的文章
ul下的li浮动,如何是ul有li的高度
查看>>
C++ primer plus
查看>>
python mysqlDB
查看>>
UVALive 3942 Remember the Word Tire+DP
查看>>
从微软的DBML文件中我们能学到什么(它告诉了我们什么是微软的重中之重)~目录...
查看>>
被需求搞的一塌糊涂,怎么办?
查看>>
c_数据结构_队的实现
查看>>
jquery 选择器总结
查看>>
Qt设置背景图片
查看>>
【阿里云文档】常用文档整理
查看>>
java中的Volatile关键字
查看>>
前端自定义图标
查看>>
实验二
查看>>
独立开发一个云(PaaS)的核心要素, Go, Go, Go!!!
查看>>
MyBatis使用DEMO及cache的使用心得
查看>>
网站文章如何能自动判定是抄袭?一种算法和实践架构剖析
查看>>
【OpenCV学习】滚动条
查看>>
ofo用科技引领行业进入4.0时代 用户粘性连续8个月远甩摩拜
查看>>
兰州青年志愿者“中西合璧”玩快闪 温暖旅客回家路
查看>>
计划10年建10万廉价屋 新西兰政府:比想象中难
查看>>