【算法】算法测试题5：牛牛的数列：最长连续子序列

MRZYD 发布于2019-08-23 11:37 / 1770人阅读

摘要：题目描述链接来源牛客网牛牛现在有一个个数组成的数列牛牛现在想取一个连续的子序列并且这个子序列还必须得满足最多只改变一个数就可以使得这个连续的子序列是一个严格上升的子序列牛牛想知道这个连续子序列最长的长度是多少。

题目描述

链接：https://www.nowcoder.com/ques...
来源：牛客网

牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,就可以使得这个连续的子序列是一个严格上升的子序列,牛牛想知道这个连续子序列最长的长度是多少。

输入描述

输入包括两行,第一行包括一个整数n(1 ≤ n ≤ 10^5),即数列的长度;
第二行n个整数a_i, 表示数列中的每个数(1 ≤ a_i ≤ 10^9),以空格分割。

输出描述

输出一个整数,表示最长的长度。

示例1

输入
6 
7 2 3 1 5 6
输出
5

解题思路

分析：这道题目看上去没法下手，就当学习一个思路吧，首先根据当前数组顺着求一遍以每个位置作为结尾的连续最长递增子序列的长度值，再逆着求解以每个元素作为开头的连续最长递增子序列的长度值，然后根据这两组值来找连接点。具体就拿体重的例子来说，此时数组arr为
7 2 3 1 5 6，我们定义两个数组left
和right，left数组表示正着求以每个元素作为结尾的最长递增子序列的长度，而right数组表示逆着以每个元素作为开头的连续最长递增子序列的长度值，所以可以知道left[0]=1,表示以7结尾的目前最长的连续递增子序列的长度值就是1，依次left[1]=1,left[2]=2,left[3]=1,left[4]=2,left[5]=3;
而right[5]=1,right[4]=2,right[3]=3,right[2]=1,right[1]=2,right[0]=1;好了，到此为止两个辅助的数组已经求出，接下来就要找连接点了，是这样的，根据题目意思，我们要找一个子序列，而且之多改变一个数就可以形成严格的连续递增子序列，所以我们先盯住数组中2这个数，我们发现以7结尾的最长的连续递增子序列的长度为left[0],而以3开头的连续递增子序列长度为right[2]，这样，我们其实不用管7和3之间的数到底是多少，是2也好，不是2也好，只要2前面的数7能够严格小于2后面的数3，说明通过改变7和3之间这个数至合适的数值则，这两部分就可以连成一个连续的严格递增子序列，所有，我们遍历所有这样的点，记录满足条件的最大的长度再加1即可。
https://blog.csdn.net/wwe4023...

JavaScript代码 JavaScript代码1（雏形）

let n = parseInt(readline());
let t1 = readline();
let t2 = new String(t1);
let line = t2.split(" ");
let arr =  new Array();
for(let i = 0; i < line.length; i++){
    arr[i] = parseInt(line[i]);
}
let left = new Array(n);
let right = new Array(n);
let ans = 0;
for(let i = 0; i < arr.length; i++){
    left[i] = computeLeft(i, arr);
}
for(let i = arr.length - 1; i >= 0; i--){
    right[i] = computeRight(i, arr);
}
for(let i = 1 ; i < arr.length-1; i++){
    if(arr[i-1] <  arr[i+1]){
        let sum = left[i-1] + right[i+1];
        if(sum > ans){
            ans = sum;
        }
    }
}

print(ans+1);

function computeLeft(pos, arr){
    let count = 1;
    for(let i = pos; i > 0; i--){
        if(arr[i] > arr[i-1]){
            count++;
        }else{
            return count;
        }
    }
    return count;
}

function computeRight(pos, arr){
    let count = 1;
    for(let i = pos; i < arr.length-1; i++){
        if(arr[i] < arr[i+1]){
            count++;
        }else{
            return count;
        }
    }
    return count;

}

JavaScript代码2（优化）

let n = parseInt(readline());
let t1 = readline();
let t2 = new String(t1);
let line = t2.split(" ");
let arr =  new Array();
for(let i = 0; i < line.length; i++){
    arr[i] = parseInt(line[i]);
}
let left = new Array(n);//以arr[i]结尾的连续序列长度
let right = new Array(n);//以arr[i]开头的连续序列长度
let ans = 0;
left[0] = 1;
right[0] = 1;
for(let i = 1; i < arr.length; i++){
    if(arr[i] > arr[i-1]){
        left[i] = left[i-1] + 1;
    }else{
        left[i] = 1;
    }
    //left[i] = computeLeft(i, arr);
}
for(let i = arr.length - 1; i >= 0; i--){
    if(arr[i] < arr[i+1]){
        right[i] = right[i+1]+1;
    }else{
        right[i] = 1;
    }
    //right[i] = computeRight(i, arr);
}
for(let i = 1 ; i < arr.length-1; i++){
    if(arr[i-1] <  arr[i+1]){
        let sum = left[i-1] + right[i+1];
        if(sum > ans){
            ans = sum;
        }
    }
}

print(ans+1);

超融合服务器服务器托管算法最大子数列最大连续子串算法最长递增子序列最长公共子序列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97220.html

[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
javascript 最长公共子序列

摘要：但不是和的最长公共子序列，而序列和也均为和的最长公共子序列，长度为，而和不存在长度大于等于的公共子序列。最长公共子序列给定序列和，从它们的所有公共子序列中选出长度最长的那一个或几个。为和的最长公共子序列长度。最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问...

Xufc 2019-08-22 13:52 评论0 收藏0
2019网易互娱数据挖掘实习生笔试部分记录

摘要：今晚做完了网易互娱数据挖掘实习生的笔试题，虽然大部分的题目都不太记得了。采样分为上采样和下采样。上采样是把小众类复制多份下采样是从大众类中剔除一些样本，或者说只从大众类中选取部分样本。今晚做完了网易互娱数据挖掘实习生的笔试题，虽然大部分的题目都不太记得了。但是还是有一些印象比较深的坑需要填一下。比起腾讯和字条跳动难度适中，不算很大，字节的笔试挂了。其实这次感觉自己做的也不是挺好哈哈哈...

Meils 2019-07-31 10:15 评论0 收藏0
【算法】算法测试题4：最长公共连续子串

摘要：问题描述链接来源牛客网给出两个字符串可能包含空格找出其中最长的公共连续子串输出其长度。示例输入输出解题思路比较两个字符串找出的子串是否在中两个指针和从头遍历到尾，找以开头的子串中最长的在中的子串。问题描述链接：https://www.nowcoder.com/ques...来源：牛客网给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。输入描述输入为两行...

MockingBird 2019-08-23 11:36 评论0 收藏0
一道算法题：求出异或和为零的最长连续子串

摘要：最近看见一道算法题，本着见题解题的学习心态解决了它，由于目前正在研究正则表达式，所以就从正则的方向入手了题目如下输入个整数，中间用空格隔开，求出异或和为的最长连续子串。要求输出子串的长度子串在输入的数组中的起始位置和结束位置。最近看见一道算法题，本着见题解题的学习心态解决了它，由于目前正在研究正则表达式，所以就从正则的方向入手了：题目如下：输入N个整数，中间用空格隔开，求出异或和为...

刘玉平 2019-07-30 18:00 评论0 收藏0