【尺取】HDU Problem Killer

acm.hdu.edu.cn/showproblem.php?pid=5328

【题意】

给定一个长度为n的正整数序列，选出一个连续子序列，这个子序列是等差数列或者等比数列，问这样的连续子序列最长是多少？

【思路】

尺取，用来解决这样的问题：需要在给的一组数据中找到不大于某一个上限的“最优连续子序列”

分别用双指针找最长的等差数列和等比数列，找最大值就可以了。

注意a 或者 a b既是等差数列，又是等比数列。

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 int n;

 const int maxn=1e6+;

 int a[maxn];

 int ans;

 int AP()

 {

     int l=;

     int r=;

     int add=a[r]-a[l];

     int res=;

     while(l<n && r<n)

     {

         while(r<n && a[r]-a[r-]==add)

         {

             r++;

         }

         res=max(res,r-l);

         l=r-;

         add=a[r]-a[l];

     }

     return res;

 }

 int GP()

 {

     int l=;

     int r=;

     double q=(double)a[r]/(double)a[l];

     int res=;

     while(l<n && r<n)

     {

         while(r<n && (double)a[r]/(double)a[r-]==q)

         {

             r++;

         }

         res=max(res,r-l);

         l=r-;

         q=(double)a[r]/(double)a[l];

     }

     return res;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++)

         {

             scanf("%d",&a[i]);

         }

         if(n<=)

         {

             printf("%d\n",n);

             continue;

         }

         ans=;

         ans=max(ans,AP());

         ans=max(ans,GP());

         printf("%d\n",ans);

     }

     return ;

  }