文章目錄

• 1 題目理解
• 2 開始思考

1 題目理解

給你一個整數數組 arr 和一個整數 difference，請你找出并返回 arr 中最長等差子序列的長度，該子序列中相鄰元素之間的差等于 difference 。
輸入：整數數組arr， 整數difference
輸出：最長等差子序列的長度
規則：這個等差子序列相鄰元素的差等于difference
示例 1：
輸入：arr = [1,2,3,4], difference = 1
輸出：4
解釋：最長的等差子序列是 [1,2,3,4]。

示例 2：
輸入：arr = [1,3,5,7], difference = 1
輸出：1
解釋：最長的等差子序列是任意單個元素。

示例 3：
輸入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
輸出：4
解釋：最長的等差子序列是 [7,5,3,1]。

2 開始思考

以arr = [1,5,7,8,5,3,4,2,1], difference = -2 為例。
處理1，子序列是[1]
處理5，因為5-1!=-1，所以產生子序列[5]，此時子序列有[1],[5]
處理7，因為7-5!=-2，7-1!=-2，所以產生子序列[7]，此時子序列有[1],[5]，[7]
處理8…，此時子序列有[1],[5],[7],[8]
處理5，因為5-8!=-2,5-7=-2,子序列變為：[1],[5],[7,5],[8]
…
所以發現，在處理每一個數的時候，和他前面已經形成的每個子序列的某位數字比較，符合條件就可以追加，不符合條件就單獨成一個子序列。當然在追加的時候肯定要選擇追加在最長的那個子序列后面。
當一個數追加到子序列之后，后面的處理就只與這個數有關系，而與子序列的具體序列無關，所以可以使用dp。
用dp[i]表示以arr[i]結尾的等差子序列的最長長度。最后結果在dp[0],dp[1]…dp[n-1]之間選擇最大的。

class Solution {public int longestSubsequence(int[] arr, int difference) {int n = arr.length;int[] dp = new int[n];dp[0] = 1;int max = 1;for(int i=1;i<n;i++){dp[i] = 1;for(int j=0;j<i;j++){if(arr[j] + difference == arr[i]){dp[i] = Math.max(dp[i],1+dp[j]);}}max = Math.max(max,dp[i]);}return max;} }

提交之后發現超時。再一思考。當處理arr[i]的時候，它等差子序列的前一個數值是確定的，一定是arr[i]-difference。也就是說，不需要關心從0到i-1，每個子序列的最長長度，只要關心以arr[i]-difference為結尾的等差子序列的長度即可。

class Solution {public int longestSubsequence(int[] arr, int difference) {int n = arr.length;Map<Integer,Integer> map = new HashMap<Integer,Integer>();int[] dp = new int[n];dp[0] = 1;map.put(arr[0],1);int max = 1;for(int i=1;i<n;i++){dp[i] = 1;int t = arr[i] - difference;if(map.containsKey(t)){dp[i] = Math.max(dp[i],map.get(t)+1);}map.put(arr[i],dp[i]);max = Math.max(max,dp[i]);}return max;} }

在做315 Count of Smaller Numbers After Self的時候，因為沒有考慮重復元素使用map，出錯了。所以現在有點猶豫，可以這樣嗎？當數值重復的時候會出錯嗎？

還是上面的例子：[1],[5],[7,5],[8]，當處理數字3的時候，3-（-2）=5，當然追加在[7,5]后面變成[7,5,3]。我們從左到右處理，當map中有5的長度的時候，5一定出現在3前面，但是至于是什么位置的5并不關心，也沒有關系。因為子序列就不一定是連續的。
再從另外一個角度考慮。如果 arr[i-3] arr[i-1] arr[i] 是一個等差序列，
那么當 arr[j]=arr[i],并且 j>i的時候，那么 arr[i-3] arr[i-1] arr[j] 也一定是一個等差序列。而且 在i到j之間，可能產生一個更長的等差序列數組。
所以map優化，以arr[i]為key沒有問題。

總結

以上是生活随笔為你收集整理的1218. 最长定差子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。