付出m个数，求这m个数能够组成的最长的等差数列

给出m个数，求这m个数能够组成的最长的等差数列
原题

http://www.51nod.com/question/index.html#!questionId=79

只想到一个O(n^2)的办法，空间也是O(n^2)，可见算不了太大的，求优化的方法，无论时间或空间。

btw，感觉还是靠分治有出路
[解决办法]
进不去这个社区啊 ！！！需要你要请我加入 嘿嘿
想认识你一下  我的qq号是：1213932667
[解决办法]
最标准的动态规划问题
[解决办法]
最标准的动态规划问题  记录 （方差，数列个数，当前数列最大值）
[解决办法]
别看了。一般情况下n^2被证明是最优了。
[解决办法]

引用:

我也找了一篇论文

http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

后面分治的方法没看懂。

另外空间上有可能优化一下么？类似滚动数组之类的，时间上还是可以接受的，但空间有点大。

引用:
别看了。一般情况下n^2被证明是最优了。

那个啊，他找的是所有长度>=k的arith progression。然后用lemma 2保证输出不会太大。
至于那个分治，他把数组分左右两半，两半都递归找出所有长度>=k/2（除了数组长度减半，这个k也减半）的a.p.，然后对于每一个找出的a.p.，看看再加上另一半的元素以后能不能伸展到>=k。
还是很好理解的，毕竟才2页的paper。
[解决办法]

引用:

关键是看他第一个问题转化就没看懂，后面看那个复杂度貌似就很不容易理解，反正阅读这类英文的论文，对我来说还是个挺大的障碍。

引用:
另外空间上有可能优化一下么？类似滚动数组之类的，时间上还是可以接受的，但空间有点大。

引用:
别看了。一般情况下n^2被证明是最优了。


那个啊，他找的是所有长度>=k的ar……

水一个,这个论文的字体太小了(我指的参考文献部分),我开到150%都看不清>_<......

查看更多 下一篇