问个优酷土豆的算法题

【 在 MengNiu 的大作中提到: 】 : 题目：从随机数数组中选取长度最长的等差数列，输出其长度即可。 : 个人用了三个for循环，复杂度都快o（n^3）了，有没有好的算法呢？大神求解 等差数列是按照顺序的么，更换顺序后是等差的可不可以？比如{7, 3, 1, 5}这种？

能想到O(n^2)的DP。但是以我现在脑残的状态。估计不对。

等差数列里的数，不需要在原数组里相连 你的解法，好像不符合题意 【 在 Lamperouge 的大作中提到: 】 : 貌似有更好的方法，每次固定起点找等差的时候，遇到不等差的停止，下次起点可以从不等差的那个元素之前的元素开始找，感觉这样的复杂度大概是O(n)? 不过是连续的那种 : [code=java] : public int AP(int[] nums) { : ...................

这样啊，我以为要连续的 【 在 youmi (邮米) 的大作中提到: 】 : 等差数列里的数，不需要在原数组里相连 : 你的解法，好像不符合题意

可不可以先排序，然后再找

可以排序 【 在 xwy4586 的大作中提到: 】 : 可不可以先排序，然后再找

可以的，主要是输出长度 【 在 whisperzzzz 的大作中提到: 】 : : 等差数列是按照顺序的么，更换顺序后是等差的可不可以？比如{7, 3, 1, 5}这种？

难道不是经典题：最长等差子序列的变种，最长等差子集？ 下面两篇都可以看 ①http://pakchoi.github.io/2015/07/01/%E6%B1%82%E6%9C%80%E9%95%BF%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97/ 在最长等差子序列的处理前，先排个序就行了。 ②http://blog.sina.com.cn/s/blog_7fcf8b630102vg4q.html

这篇也可以。http://www.chenguanghe.com/google-longest-arithmetic-sequence-%E6%B1%82%E6%9C%80%E9%95%BF%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97/ 也是处理前套一个排序即可