题目解析:
本题要求解的是排序子序列,排序子序列为非递增或者非递减,很多同学在这个非递增、非递减问题上很纠结,注意:非递减就是a[i]<=a[i+1],递减就是a[i]>a[i+1],非递增就是a[i]>=a[i+1],递增就是a[i]<a[i+1]。
解题思路:
通过上面理解了排序子序列,这个题的本质就是去找这里图里面的波峰和波谷。但是存在一个特殊情况,就是如果波峰有两个,但是只有四个数,由于数列最少是两个数,所以只能分成两个子序列,而不是三个。
图解思路:
一般情况: 特殊情况
直接上代码
#include <iostream>
#include <vector>
using namespace std
;
int main()
{
int num
= 0;
vector
<int> arr
;
int ret
= 1;
cin
>> num
;
arr
.resize(num
);
for(int i
= 0; i
< num
; i
++)
cin
>> arr
[i
];
for(int i
= 1; i
< num
-1; ++i
)
{
if((arr
[i
-1] > arr
[i
] && arr
[i
] < arr
[i
+1])
|| (arr
[i
-1] < arr
[i
] && arr
[i
] > arr
[i
+1]))
{
ret
++;
if(i
!= num
-3)
i
++;
}
}
cout
<< ret
<< endl
;
return 0;
}