NYOJ 370 波動序列

波動序列 時間限制：1000 ms  |  內存限制：65535 KB 難度：2 描述 有一個長度為N的整數序列，序列裡面的數是兩兩不同的，現在要在裡面找一個波動序列，這個序列越長越好。 比如有波動序列{a0,a1,a2…an-1},則a0 > a1 < a2 > a3 < … 輸入 第一行輸入一個數T，代表有T個任務,T不大於50。 對於每個任務，輸入格式為 N a0 a1 a2 … aN-1  其中N<=30000，測試數據保證序列的數兩兩不同。 輸出 對於每個任務，輸出最長的波動序列長度 樣例輸入 4 5 1 2 3 4 5 5 5 4 3 2 1 5 5 1 4 2 3 5 2 4 1 3 5 樣例輸出 1 2 5 3

/*讀完這個題，我的第一感覺是：這是個dp問題。如果用普通方法做，時間復雜度是O(n^2),會超時。
  後來想了一下，只需要判斷是遞增或遞減就行了，O(n)時間復雜度。
  即：對於當前的點，1、如果要找遞增序列：如果下一個點比當前的點大，序列長度加1，更新下一個點為當前點；
                如果下一個點比當前點小，長度不變，同樣更新下一個點為當前點，而且有利於找出遞增序列
                找遞減序列的方法與找遞增序列的方法一致。*/
#include<stdio.h>
int a[30003];
int main()
{
    int T,N,i,flag,len,now;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(i=0;i<N;i++)
            scanf("%d",&a[i]);
        now=a[0];
        flag=1;/*flag=0表示要找遞增序列，flag=1表示要找遞減序列*/
        len=1;
        for(i=1;i<N;i++)
        {
            if(!flag&&a[i]>now)
            {
                flag=1;
                len++;
            }
            else if(flag&&a[i]<now)
            {
                flag=0;
                len++;
            }
            now=a[i];
        }
        printf("%d\n",len);
    }
    return 0;
}