題目連結:
題目意譯:
給定一個整數陣列 nums,回傳 nums 中最長的等差子序列之長度。
注意到:
一個子序列為可以從另一個陣列藉由刪除其中若干個元素(可以是零個)且不更動剩餘元素的相對順序而得到的一個陣列。
一個子序列 seq 如果滿足 seq[i + 1] - seq[i] 對於所有 i 值都成立(0 ≦ i < seq.length - 1),則該子序列為「等差」的。
限制:
2 ≦ nums.length ≦ 1000
0 ≦ nums[i] ≦ 500
範例測資:
範例 1:
輸入: nums = [3,6,9,12]
輸出: 4
解釋: 整個陣列即為一個等差子序列,其公差為 3。
範例 2:
輸入: nums = [9,4,7,2,10]
輸出: 3
解釋: 最長的子序列為 [4,7,10]。
範例 3:
輸入: nums = [20,1,15,3,10,5,8]
輸出: 4
解釋: 最長的子序列為 [20,15,10,5]。
解題思維:
把
這題的條件變成是「每一項與前一項之差值恰好為 d」且數值範圍變大(不再限於字母表,而是 0 ~ 500 之間的數字)之後,這便是本題固定公差為 d 時的解法。
而我們接下來只要窮舉出所有可能的公差,然後取所有等差子序列中的最長之長度即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。