k217 - 11240 - Antimonotonicity
題目描述
題目要求找出一個給定序列中最長的反單調子序列，該子序列的元素必須交替地大於和小于前一個元素。更具體地說，子序列需要滿足 Mary[0] > Mary[1] < Mary[2] > Mary[3] < ... 的條件。
解題思路
此題可以使用貪心演算法解決。我們從序列的第一個元素開始，並根據當前子序列的長度是奇數還是偶數來決定如何選擇下一個元素。如果子序列長度是奇數，我們希望選擇一個小于當前最大值的元素；如果子序列長度是偶數，我們希望選擇一個大于當前最小值的元素。我們維護一個 tmp 變數來追蹤當前最大值或最小值，並根據選擇的元素更新它。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
long long t,n,x;
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(0);
cin >> t;
while(t--){
cin >> n;
long long ans=0,tmp=-1e9;
for(int i=0;i<n;++i){
cin >> x;
if(ans%2){
if(x<tmp){
tmp=x;
++ans;
}
else{
tmp=max(x,tmp);
}
}
else{
if(x>tmp){
tmp=x;
++ans;
}
else{
tmp=min(x,tmp);
}
}
}
cout << ans << "\n";
}
}