贪心:O(n)
其实就是找到一个最长的波浪序列(每一盆花都是波峰或波谷)。
首先,对于第一盆花,不论如何都要选,因为如果不选,第二盆花就相当于第一盆,而花的总数却减少了,所以一定不会更优。
对于第二盆花,如果和第一盆等高,就没有用,可以直接不选(这时候还是找第二盆);如果比第一盆高,那么它就一定要作为波峰(如果作为波谷则等同于第一盆没选);同理如果比第一盆低就一定是波谷。
对于后面的花,如果找波峰,如果当前花比上一盆高,那么波峰就找到了,接下来找波谷;如果不如上一盆高,那么用这盆更低的花继续找波峰结果一定不会更差。找波谷同理。
在操作过程中记录留下多少花即可。
蒟蒻模拟出来的做法,感觉有点单调栈的味道
#include <iostream>
#include <stack>
using namespace std;
const int N = 100010;
int n;
int a[N];
stack<int> s, t;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++) //记录满足条件A的最长长度
{
if(s.empty())
{
s.push(a[i]);
continue;
}
if(s.size() % 2 != 0)
{
if(a[i] >= s.top())
{
s.pop();
s.push(a[i]);
}
else{
s.push(a[i]);
}
}
else{
if(a[i] > s.top())
{
s.push(a[i]);
}
else{
s.pop();
s.push(a[i]);
}
}
// cout << i << endl;
}
int ans = s.size();
for(int i = 1; i <= n; i++) //记录满足条件B的最长长度
{
if(t.empty())
{
t.push(a[i]);
continue;
}
if(t.size() % 2 != 0)
{
if(a[i] <= t.top())
{
t.pop();
t.push(a[i]);
}
else{
t.push(a[i]);
}
}
else{
if(a[i] < t.top())
{
t.push(a[i]);
}
else{
t.pop();
t.push(a[i]);
}
}
}
int res = t.size();
ans = max(ans, res);
cout << ans;
return 0;
}