/**
* @param {number[]} A
* @return {number}
*/
let longestArithSeqLength = function (A) {
let dp = []
let n = A.length
if (!n) {
return 0
}
let max = 0
dp[n - 1] = { 0: 0 }
for (let i = n - 2; i >= 0; i--) {
dp[i] = {}
let cur = A[i]
for (let j = i + 1; j < n; j++) {
let diff = A[j] - cur
let maxLength = (dp[j][diff] || 0) + 1
let maxIDiff = Math.max(dp[i][diff] || 0, maxLength)
dp[i][diff] = maxIDiff
max = Math.max(max, maxIDiff)
}
}
return max + 1
};
给定一个整数数组 A,返回 A 中最长等差子序列的长度。
回想一下,A 的子序列是列表
A[i_1], A[i_2], ..., A[i_k]
其中0 <= i_1 < i_2 < ... < i_k <= A.length - 1
。并且如果B[i+1] - B[i]( 0 <= i < B.length - 1)
的值都相同,那么序列B
是等差的。来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-arithmetic-sequence 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
从后往前求 dp 的规划数组,对于每一项都要求从本项开始,一直循环到结尾,记录每个相对每个值的差的等差数列长度。
注意由于这个问题的最优解等差数列的起点不一定在第一项,所以需要在每次求解的时候都去更新全局变量
max
,最后直接返回这个max
,而不是最后再对数组进行遍历求解,否则会增加复杂度。