本文共 2545 字，大约阅读时间需要 8 分钟。

题：求随机数构成的数组中找到长度大于=3的最长的等差数列

输出等差数列由小到大: 

如果没有符合条件的就输出[0,0]

格式：

输入[1,3,0,5,-1,6]

输出[-1,1,3,5]

要求时间复杂度，空间复杂度尽量小

分析：基本算法思路（采用动态规划思想）：首先，只要得到数列的公差和一个首项就可以确定一个等差数列，因此我们要寻找最长等差数列的公差以及首项。其次，为了方便查找公差和首项，我们应该将原数组进行由小到大排序，这样各两数之间的公差也是成递增形势的，这样我们就可以避免回溯查找首项。

因此，在搜寻公差及首项的过程中，我们可以分两三个决策阶段：

1、如果公差为0，应该做何处理。

2、如果公差不为0，应该做何处理。

3、如果找到的数列长度是当前最长的做相应的处理

      针对以上情况，我们应该选择一种合适的数据结构——平衡排序树，stl中的set，map，mutiset，multimap是以红黑树结构为形势的容器，无疑是非常合适的，根据题目情况，可能存在具有相同元素的数组，因此我们选择multiset，这样无论我们对数据进行插入排序，查找都是比较高效的，因此总体上是可以满意的。

      最后有几项时间上的优化不在这里说明，详情可看代码。若有不足之处，望能不吝指出！^_^

我的实现代码：

先确定首项a和公差c，然后在multiset中查找是不是存在 a+c*n

/**Author:花心龟Blog：http://blog.csdn.net/zhanxinhang**/#include 
   
    #include 
    
     #include 
     
      using namespace std;void show_longest_seq(const multiset
      
       & myset){	int maxLength = 0, curr_pos = 0, curr_d = 0, counter=0,i=0; //一些辅助变量	int d_result, a1_result; //存储最长等差数列的公差以及首项	multiset
       
        ::const_iterator set_it1,set_it2;		/*	     (主题)寻找长度最长的等差数列,最坏情况下时间复杂度为O(n^3)	*/	for(set_it1 = myset.begin(); set_it1 != myset.end();)	{		for(set_it2=set_it1,set_it2++; set_it2 != myset.end();)//第二层循环从set_it1所指的下一个元素开始遍历		{			curr_d = *set_it2 - *set_it1; //算得当前公差，注意由于set为自排序容器，从小到大排列，所以curr_d恒为正			if(curr_d == 0) // 如果公差为0			{				counter = myset.count(*set_it1);				set_it2 = myset.upper_bound(*set_it1);//(优化项)跳过与set_it1相等的元素			}			else			{				counter = 2; //（优化项）最小长度要求要不小于所以直接从开始累加				while(myset.find(*set_it1 + counter*curr_d) != myset.end()) //计算数列项个数					++counter;				set_it2 = myset.upper_bound(*set_it2);// （优化项）跳过与*set_it2相等的元素			}						if(counter > maxLength)  //如果新数列长度大于maxLength			{				d_result = curr_d;				a1_result = *set_it1;                        maxLength = counter;			}		}		curr_pos += myset.count(*set_it1);     //计算第一层循环遍历到的当前位置		if(myset.size()-curr_pos < maxLength)  // (优化项)如果集合中剩下的元素小于最大数列长度，就退出循环			break;		set_it1 = myset.upper_bound(*set_it1); //下一次set_it1 的位置，并跳过相同元素	}	/*	   打印最长等差数列	*/	if(maxLength <= 2)	{		cout<<"longest_seq：[0,0]"<