等差数列 — 编程爱好者社区

主题：等差数列

593170024 [专家分：500] 发布于 2010-08-13 21:54:00

等差数列（aseq）
【问题描述】
给定n(1<=n<=5000)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.
【输入数据】
第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.
【输出数据】
对于每个输入数据,输出你所找出的最长等差数列的长度
输入样例
Aseq.in
7
3
8
4
5
6
2
2
输出样例
Asep.out
5

本帖地址： http://bbs.pfan.cn/post/347491.html

回复列表（共6个回复）

沙发

小田甜 [专家分：3910] 发布于 2010-08-14 03:16:00

除了暴力以外没想到什么好办法。
开个大数组，fillchar 0；
每次a[n,a[n]-a[i]]=max(a[i,a[n]-a[i]]+1,2)，如果大于maxnum则覆盖，
最后输出maxnum。
（好像可以美其名曰动规的）
O (n^2)
好像大了些，不过不知道有什么别的方法。

板凳

cgl_lgs [专家分：21040] 发布于 2010-08-15 22:41:00

读入；
排序；
求相临数的差；
后面儿自个儿想想吧：）

3 楼

小田甜 [专家分：3910] 发布于 2010-08-15 23:57:00

哦，谢谢，我忘了吧、排序了。

4 楼

593170024 [专家分：500] 发布于 2010-10-07 00:27:00

暴搜超时吧？

5 楼

cgl_lgs [专家分：21040] 发布于 2010-10-08 23:07:00

應該還好吧，排完序后應該工作量會很小。

6 楼

969519450 [专家分：0] 发布于 2010-10-17 16:18:00

仔细分析分析，有点简单。
总结一下其他高手的评语。

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：等差数列

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：等差数列

回复列表 （共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共6个回复）