最长等差数列问题

以排好序的数组，找出数组最长等差数列的长度，比如
1 3 5 6 8 9 10 12 13 14
最长等差数列为6 8 10 12 14

1 把数组每个元素分别+1，+2，。。。，+(a[len-1]-a[i])，
2 每次update能组成的最长等差数列的元素个数，和公差
3 从而得到最长的等差数列的公差输出

没想到很好的办法。。

常规解法的时间复杂度是n^3, 也就是先确定等差数列头两个元素， a, a[j],再往后搜索以这两个元素开头的所有满足条件的数列，这样就存在了重复计算，因该可以用DP优化。比如我选择了a[0]和a[1], 那么我可能要搜索从a[2]一直到a[n-1]的所有元素，当我选择a[0],a[2]时，可能要搜索所有a[3]一直到a[n-1]的所有元素，存在重复计算。

DP状态转移公式：
设F(i,j)为以数列a[i],a[j]结尾的等差数列，i<j，则
F(i,j) = {1 +  F(x,i) if (x存在), 2 if (x不存在) }
其中x可以用二分来查找，n^2*logn[/i]

1. 
   
2. int BinarySearch(int a[], int n, int nVal)
   
3. {
   
4.         assert(a);
   
5.         if (0 == n) return -1;
   
6. 
   
7.         int nBeg = 0;
   
8.         int nEnd = n-1;
   
9. 
   
10.         while (nBeg <= nEnd)
    
11.         {
    
12.                 int nMid = (nBeg+nEnd)/2;
    
13.                 if (a[nMid] == nVal)
    
14.                         return nMid;
    
15. 
    
16.                 if (a[nMid] > nVal)
    
17.                         nEnd = nMid-1;
    
18.                 else
    
19.                         nBeg = nMid+1;
    
20.         }
    
21. 
    
22.         return -1;
    
23. }
    
24. 
    
25. int GetLength(int a[], int n)
    
26. {
    
27.         assert(a && n>0);
    
28. 
    
29.         int** pDP = new int*[n];
    
30.         for (int i = 0; i < n; i++)
    
31.         {
    
32.                 pDP[i] = new int[n];
    
33.                 memset(pDP[i], 0, sizeof(int)*n);
    
34.         }
    
35. 
    
36.         int nMax = 0;
    
37.         for (int i = 0; i < n; i++)
    
38.         {
    
39.                 for (int j = i+1; j < n; j++)
    
40.                 {
    
41.                         int nDiff = a[j]-a[i];
    
42.                         int nIndex = BinarySearch(a, i, a[i]-nDiff);
    
43. 
    
44.                         if (nIndex >= 0)
    
45.                                 pDP[i][j] = pDP[nIndex][i]+1;
    
46.                         else
    
47.                                 pDP[i][j] = 2;
    
48. 
    
49.                         nMax = pDP[i][j] > nMax ? pDP[i][j] : nMax;
    
50.                 }
    
51.         }
    
52. 
    
53.         for (int i = 0; i < n; i++)
    
54.                 delete pDP[i];
    
55.         delete []pDP;
    
56. 
    
57.         return nMax;
    
58. }
    

复制代码