解决方案
方法一:使用 Set 的暴力法
思路
每个斐波那契式的子序列都依靠两个相邻项来确定下一个预期项。例如,对于 2, 5
,我们所期望的子序列必定以 7, 12, 19, 31
等继续。
我们可以使用 Set
结构来快速确定下一项是否在数组 A
中。由于这些项的值以指数形式增长,最大值 的斐波那契式的子序列最多有 43 项。
算法
对于每个起始对 A[i], A[j]
,我们保持下一个预期值 y = A[i] + A[j]
和此前看到的最大值 x = A[j]
。如果 y
在数组中,我们可以更新这些值 (x, y) -> (y, x+y)
。
此外,由于子序列的长度大于等于 3 只能是斐波那契式的,所以我们必须在最后进行检查 ans >= 3 ? ans : 0
。
复杂度分析
-
时间复杂度:,其中 是
A
的长度, 是A
中的最大值。 -
空间复杂度:,集合(set)
S
使用的空间。
方法二:动态规划
思路
将斐波那契式的子序列中的两个连续项 A[i], A[j]
视为单个结点 (i, j)
,整个子序列是这些连续结点之间的路径。例如,对于斐波那契式的子序列 (A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] = 13)
,结点之间的路径为 (1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10)
。
这样做的动机是,只有当 A[i] + A[j] == A[k]
时,两结点 (i, j)
和 (j, k)
才是连通的,我们需要这些信息才能知道这一连通。现在我们得到一个类似于 最长上升子序列 的问题。
算法
设 longest[i, j]
是结束在 [i, j]
的最长路径。那么 如果 (i, j)
和 (j, k)
是连通的, longest[j, k] = longest[i, j] + 1
。由于 i
由 A.index(A[k] - A[j])
唯一确定,所以这是有效的:我们在 i
潜在时检查每组 j < k
,并相应地更新 longest[j, k]
。
复杂度分析
-
时间复杂度:,其中 是
A
的长度。 -
空间复杂度:,其中 是
A
中最大的元素。我们可以证明子序列中的元素数量是有限的(复杂度 ,其中 是子序列中最小的元素)。