图一乐解法,在这个数据范围下和暴力运行时间只差1ms
up[i]
表示以a[i]
结尾并且是前一个数字上升得到的最长子序列数。
down[i]
表示以a[i]
结尾并且是前一个数字下降得到的最长子序列数。
当j > i
时:
若a[j] <= a[i]
,则有down[j] >= down[i]
,此时down[i]
将永远不被使用;
同理,若a[j] >= a[i]
,则有up[j] >= up[i]
此时up[i]
将永远不被使用;
故使用两个单调栈,一个维护上升序列,一个维护下降序列。
此时,up[i]
为上升单调栈中down
值最大者+1,down[i]
同理,故使用两个大根堆,分别存储上升单调栈中的down
值以及下降单调栈中的up
值。令开两个布尔数组表示某个元素是否在单调栈中,防止大根堆输出已经出栈的元素。
时间复杂度:分析不出来,但是肯定比$O(n^2)$更优。
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 60;
int a[N], up[N], down[N], n;
stack<int> ascend, descend;
bool ast[N], dst[N];
priority_queue<PII> ah, dh;
int main() {
int i;
cin >> n;
for (i = 0; i < n; i++) {
cin >> a[i];
// 计算up
while (ascend.size() && a[i] <= a[ascend.top()]) {
ast[ascend.top()] = false;
ascend.pop();
}
if (ascend.empty()) up[i] = 1;
else {
while (!ast[ah.top().second]) ah.pop();
up[i] = ah.top().first + 1;
}
ascend.push(i);
ast[i] = true;
// 计算down
while (descend.size() && a[i] >= a[descend.top()]) {
dst[descend.top()] = false;
descend.pop();
}
if (descend.empty()) down[i] = 1;
else {
while (!dst[dh.top().second]) dh.pop();
down[i] = dh.top().first + 1;
}
descend.push(i);
dst[i] = true;
// 入堆
ah.push({down[i], i});
dh.push({up[i], i});
}
int r = 0;
for (i = 0; i < n; i++) {
r = max(r, up[i]);
r = max(r, down[i]);
}
cout << r;
return 0;
}