给定一个未排序数组, 找出其中最长的等差数列

92 阅读 0 评论 61 点赞

我是靠谱客的博主忧伤鸡，最近开发中收集的这篇文章主要介绍给定一个未排序数组, 找出其中最长的等差数列，觉得挺不错的，现在分享给大家，希望可以做个参考。

转载请注明来自souldak，微博:@evagle

题目如题所诉：其实就是前面那篇leetcode 最长连续序列 longest consecutive sequence 的升级版

leetcode上的题目是要求等差为1，即连续序列，而现在把等差为1的限制条件去掉，找最长的等差数列，做法和复杂度却升级了。

现在给出一个O(n^2)的算法：

算法思路：

先排序，O(NlogN)

从后往前，对于a[i],令 j=i+1~n-1

map[pair(a[i],a[j]-a[i])] = max(map[pair(a[j]-,a[j]-[a[i])] , 1) + 1

其中pair(a,b)表示以a为首项，b为等差的等差数列的最长的长度

从a[n-1]一直算到a[0],所有的pair(a[k],b)都算出来了，现在只要找出其中最大的即可。

按着这个思路，代码实现也比较简单，就不上代码了。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。