原題

給定未排序的數(shù)組，請給出方法找到最長的等差數(shù)列。

分析

題目描述比較簡單，但是有一個問題我們需要首先搞清楚：等差數(shù)列中的數(shù)字，是否要和原始數(shù)組中的順序一致。題目中，并沒有說明，這個就需要大家在面試的過程中和面試官進行交流。我們在這里對兩種情況都進行討論：

保證數(shù)字的順序

等差數(shù)列是要求相鄰兩個元素之間的差是相同的。那我們可以記錄下來數(shù)組中任意兩個數(shù)的差，并且記錄下來。對于數(shù)組A，記錄A[j]-A[i]，其中 i

構(gòu)造hashmap如下：

-1=>(0,1)(1,2)

1=>(2,3)(4,5)

3=>(3,4)

上面已經(jīng)排好序，對于第一個，找到等差數(shù)列0,1,2對應(yīng)數(shù)字誒5,4,3.第二個，3和4位置沒有連起來，不夠成等差數(shù)列。方法平均時間復(fù)雜度為O(n^2),空間復(fù)雜度為O(n^2).

無需保證數(shù)字的順序

不需要保證數(shù)字的順序與原來數(shù)組一致，如何找到最長的等差數(shù)列呢？原來的數(shù)組是無序的，我們先對數(shù)組進行排序，最終的一定是排序之后序列的子序列。然后，我們采用動態(tài)規(guī)劃的方法解決這個問題。

我們假設(shè)dp[i][j]表示以A[i]A[j]開始的數(shù)列的長度(數(shù)列的前兩項)，dp[i][j]如何表示呢？dp[i][j]=dp[j][k]+1，當 A[j]-A[i]=A[k]-A[j],及A[k]+A[i]=2*A[j]。根據(jù)dp[i][j]的定義，我們知道dp[x][n-1]=2，也就是 最后一列是2，數(shù)列只有A[x]和A[n-1]兩個元素。首先，j從n-2，開始向前遍歷，對于每一個，找到i和k，滿足 A[k]+A[i]=2*A[j]，則有dp[i][j]=dp[j][k]+1，若沒有，則dp[i][j]就為2.

這里找i和k，有一個小技巧，如下：初始i=j-1,k=j+1，然后分別向兩邊遍歷，如果A[k]+A[i]=2*A[j]則i--。大家還是參考代碼吧：

總結(jié)

以上是生活随笔為你收集整理的最长等差数列_最长等差数列分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。