当前位置: 代码迷 >> 综合 >> poj 3298 Antimonotonicity 贪心
  详细解决方案

poj 3298 Antimonotonicity 贪心

热度:23   发布时间:2024-01-19 06:04:05.0

题意:

求一个序列的最大子序列,该子序列满足:a1>a2<a3>a4.....。

分析:

贪心,从极大值起交替取这个序列中极小值、极大值。

代码:

//poj 3298
//sep9
#include <iostream>
using namespace std;
const int maxN=30024;
int a[maxN];int main()
{int cases;scanf("%d",&cases);while(cases--){int i,j,n,s=0;scanf("%d",&n);for(i=1;i<=n;++i)scanf("%d",&a[i]);int ans=1;	for(i=1;i+1<=n;++i){if(a[i]>a[i+1]){s=0;	++ans;for(j=i+1;j+1<=n;++j){if((s==0&&a[j]<a[j+1])||(s==1&&a[j]>a[j+1])){++ans;s=s^1;}			}break;}}printf("%d\n",ans);}return 0;	
} 


  相关解决方案