题意:给一段序列,求连续的子序列中最长的等差数列或者等比数列的长度。

解法:O(n)的扫两遍一次判等差一次判等比就好了。

代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
using namespace std;
int a[1000005];
bool equal(int a1, int a2, int b1, int b2)
{
int r1 = __gcd(a1, a2), r2 = __gcd(b1, b2);
a1 /= r1;
a2 /= r1;
b1 /= r2;
b2 /= r2;
return a1 == b1 && a2 == b2;
}
int main()
{
int T;
while(~scanf("%d", &T))
{
while(T--)
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = 1;
int flag = 0;
int res = 2;
for(int i = 2; i <= n; i++)
{
if(!flag)
{
res = 2;
flag = 1;
ans = max(res, ans);
}
else
{
if(a[i] - a[i - 1] == a[i - 1] - a[i - 2])
{
res++;
ans = max(ans, res);
}
else
{
flag = 0;
i--;
}
}
}
flag = 0;
res = 2;
for(int i = 2; i <= n; i++)
{
if(!flag)
{
res = 2;
flag = 1;
ans = max(res, ans);
}
else
{
if(equal(a[i], a[i - 1], a[i - 1], a[i - 2]))
{
res++;
ans = max(ans, res);
}
else
{
flag = 0;
i--;
}
}
}
printf("%d\n", ans);
}
}
return 0;
}

  

最新文章

  1. Android入门(四):链接接口组件和程序代码
  2. easyui datagird 列宽自适应
  3. .NET 自带的动态代理+Expression 实现AOP
  4. wc命令--Linux统计文件行数
  5. Python:数字
  6. 【转】iOS-延迟操作方法总结
  7. LintCode 38. Search a 2D Matrix II
  8. VS2012执行Cocos2d-xTest案例载入失败解决方式
  9. [Javascript] Querying an Immutable.js Map()
  10. B-JUI(Best jQuery UI) 前端框架
  11. div中显示某个网页
  12. c++ split()实现
  13. 网络与WEB 编程
  14. ApplicationContextAware 接口的作用
  15. php去除数组中重复值,并返回结果!
  16. webuploader在ie9以下失效原因
  17. Linux之vi/vim编辑器
  18. Socket网络编程--聊天程序(4)
  19. Django框架----权限管理(设计分析以及具体细节)
  20. mediawiki 安装 部署 配置 使用学习

热门文章

  1. UITableViewCell 重合问题解决方法
  2. iOS 基础 第二天(0805)
  3. python 新时代
  4. C# - Generic
  5. 4.4 spring-自定义标签的解析
  6. C#取中间文本
  7. PAT-乙级-1041. 考试座位号(15)
  8. PAT-乙级-1030. 完美数列(25)
  9. Good Bye 2015 A
  10. Notepad++ 右键菜单自定义配置