排序子序列

    xiaoxiao2022-06-26  83

    题目解析:

      本题要求解的是排序子序列,排序子序列为非递增或者非递减,很多同学在这个非递增、非递减问题上很纠结,注意:非递减就是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; }

    最新回复(0)