/*
算法思想:
使用数列arr={7 2 3 1 5 6}为例,
假设所求最长长度为max
1.先将数列分为一系列有序子序列,对应例子为{7}, {2,3},{1,5,6},
2.然后遍历一遍这些子序列,对于任意两个序列的首尾元素,判断:当去掉前一个序列的尾元素时或者去掉后一个序列的首元素时,
两个序列能否拼成严格递增的数列,如果可以,那么max = (length(前一序列) + length(后一序列), max)
实际的做法:
对于数组arr的每个元素,都记录了值,相同序列标记flag(用来标记是否同一序列,其实有点多余,不过我是为了方便而这么做),
从此处开始的顺序子序列的最长长度start_count, 从此处结束的顺序子序列最长长度end_count
1.先遍历一遍数组arr,填充arr每个元素的val, start_count, end_count,这样就将整个序列分为若干个有序序列了
2.一次遍历,更新max的值,即结束
*/
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
typedef unsigned int uint;
struct node{
uint val; //数列的值
uint flag;//辅助作用,为每个顺序子序列作标记,每个顺序子序列有一个唯一标志
uint start_count; //从此处开始的顺序子序列的最大长度
uint end_count;//从此处结束的顺序子序列的最大长度
};//arr每个元素对应要记录的数据
node arr[100005]; //由于n <= 100000,为了方便直接申请足够的空间
int main(){
uint n;
cin >> n;
if(!n){ //处理边界情况
cout << 0;
return 0;
}
else if(n == 1){ //处理边界情况
cout << 1;
return 0;
}
uint temFlag = 0; //方便标志顺序子序列
cin >> arr[0].val; //先处理首元素
arr[0].flag = temFlag++; //先处理首元素
for(int i = 1;i < n;i++){
cin >> arr[i].val;
if(arr[i - 1].val < arr[i].val){ //如果此元素跟上一个元素同属一个顺序子序列,那么有相同的标志
arr[i].flag = arr[i - 1].flag;
}
else{ //此元素跟上一个元素属于不同的顺序子序列时
arr[i].flag = temFlag++; //赋予新的标志
//是时候来对上一个顺序子序列的元素的start_count,end_count进行记录了
int j = i - 1;
for(;j >= 0;j--){ //找到上一个顺序子序列的范围
if(arr[j].flag != arr[i - 1].flag)
break;
}
j++; //已找到上一个顺序子序列的范围,为j<=k<=i-1
for(int k = j;k <= i - 1;k++){
arr[k].start_count = i - k;
arr[k].end_count = k - j + 1;
}
}
}
//循环结束后,还有最后一个顺序子序列还没处理,所以要在这里进行处理
int j = n - 1;
for(;j >= 0;j--){
if(arr[j].flag != arr[n - 1].flag)
break;
}
j++;
for(int k = j;k <= n - 1;k++){
arr[k].start_count = n - k;
arr[k].end_count = k - j + 1;
}
//最后一个顺序子序列已经处理
/*再进行一次遍历,更新max的值就可以了,我在这里对每一个元素都处理了,其实没这个必要,实际上只需要对每个顺序子序列的首尾元素进行处理
就可以了*/
int tem = 0;
int ans = 0;
for(int i = 0;i < n;i++){
if(!i && i + 1 < n){ //对于首元素
tem = 1 + arr[i + 1].start_count;
}
else if(i && i + 1 < n){ //对于中间元素
if(arr[i - 1].val < arr[i + 1].val){
tem = arr[ i - 1].end_count + 1 + arr[i + 1].start_count;
}
else
tem = max(arr[i - 1].end_count + 1, arr[i + 1].start_count + 1);
}
else //对于尾元素
tem = arr[i - 1].end_count + 1;
if(tem > ans){
ans = tem;
}
}
cout << ans; //输入答案
return 0;
}
全部评论
(0) 回帖