[Swift]LeetCode873. 最长的斐波那契子序列的长度 | Length of Longest Fibonacci Subsequence

概述A sequence X_1, X_2, ..., X_n is fibonacci-like if: n >= 3 X_i + X_{i+1} = X_{i+2} for all i + 2 <= n Given a strictly increasing array A of positive integers forming a sequence, find the length of th

A sequence X_1,X_2,...,X_n is fibonacci-like if:

n >= 3 X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence,find the length of the longest fibonacci-like subsequence of A.  If one does not exist,return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A,without changing the order of the remaining elements.  For example, [3,5,8] is a subsequence of [3,4,6,7,8].) 

Example 1:

input: [1,2,3,8]Output: 5Explanation:The longest subsequence that is fibonacci-like: [1,8].

Example 2:

input: [1,11,12,14,18]Output: 3Explanation:The longest subsequence that is fibonacci-like:[1,12],[3,14] or [7,18]. 

Note:

3 <= A.length <= 1000 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9 (The time limit has been reduced by 50% for submissions in Java,C,and C++.)

如果序列 X_1,X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3,8] 是 [3,8] 的一个子序列） 

示例 1：

输入: [1,8]输出: 5解释:最长的斐波那契式子序列为：[1,8] 。

示例 2：

输入: [1,18]输出: 3解释:最长的斐波那契式子序列有：[1,12]，[3,14] 以及 [7,18] 。 

提示：

3 <= A.length <= 1000 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9 （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

228ms

 1 class Solution { 2     func lenLongestFibSubseq(_ A: [Int]) -> Int { 3  4         var dic = [Int:Int]() 5         for item in 0..<A.count{ 6             dic[A[item]] = item 7         } 8  9         var dp = [[Int]](repeating:[Int](repeating: 0,count: A.count),count: A.count)10         var result = 011         for i in 0..<A.count {12             for j in 0..<i{13                 if A[i] - A[j] < A[j] && dic[A[i] - A[j]] != nil {14                     dp[j][i] = dp[dic[A[i] - A[j]]!][j] + 115                     result = max(result,dp[j][i])16                 }17             }18         }19         return result > 0 ? result + 2 : 020     }21 }

236ms

 1 class Solution { 2     func lenLongestFibSubseq(_ A: [Int]) -> Int { 3         var map = [Int: Int]() 4         for (index,a) in A.enumerated() { 5             map[a] = index 6         } 7          8         var result = 0 9         var dp = [[Int]](repeating: [Int](repeating: 2,count: A.count)10         for i in 0 ..< A.count {11             for j in i+1 ..< A.count {12                 let a = A[i],b = A[j],c = b - a13                 if map[c] != nil {14                     if map[c]! >= i {15                         break16                     }17                     dp[i][j] = dp[map[c]!][i] + 118                     result = max(result,dp[i][j])19                 }20             }21         }22         23         return result24     }25 }

368ms

 1 class Solution { 2     func lenLongestFibSubseq(_ A: [Int]) -> Int { 3         let N = A.count 4         var indexMap = [Int: Int]() 5         for i in 0..<N { 6             indexMap[A[i]] = i 7         } 8          9         var longestMap = [Int: Int]()10         var ans = 011         12         for k in 0..<N {13             for j in 0..<k {14                 guard let i = indexMap[A[k] - A[j]] else {15                     continue16                 }17                 if i < j {18                     var temp = 019                     if let cand = longestMap[i * N + j] {20                         temp = cand + 121                     } else {22                         temp = 323                     }24                     longestMap[j * N + k] = temp25                     ans = max(ans,temp)26                 }27             }28         }29         30         return ans >= 3 ? ans : 031     }32 }

376ms

 1 class Solution { 2     func lenLongestFibSubseq(_ A: [Int]) -> Int { 3         var n = A.count,res = 0 4         var dp = [[Int]](repeating: [Int](repeating: 2,count: n),count: n) 5         var m = [Int: Int]() 6         for i in 0..<n { 7             m[A[i]] = i 8         } 9         for j in 1..<n {10             for i in 0..<j {11                 if let IDx = m[A[j] - A[i]],IDx < i {12                     dp[i][j] = max(dp[i][j],dp[IDx][i] + 1)13                     res = max(res,dp[i][j])14                 } 15             }16         }17         return res18     }19 }

388ms

 1 class Solution { 2     func lenLongestFibSubseq(_ A: [Int]) -> Int { 3         let set = Set(A) 4         var res = 0 5         for i in 0 ..< A.count { 6             for j in i + 1 ..< A.count { 7                 var a = A[i] 8                 var b = A[j] 9                 var c = a + b10                 var size = 211                 while set.contains(c) {12                     size += 113                     res = max(res,size)14                     a = b15                     b = c16                     c = a + b17                 }   18             }19         }20         return res21     }22 }

392ms

 1 class Solution { 2     func lenLongestFibSubseq(_ A: [Int]) -> Int { 3         let N = A.count 4         if N <= 2 { return N } 5          6         var map = [Int: Int]() 7         for i in 0..<N { map[A[i]] = i } 8  9         var res = 010         var dp = Array(repeating: Array(repeating: 2,count: N),count: N)11         for i in (0..<N - 1).reversed() {12             for j in (i + 1..<N) {13                 if let k = map[A[i] + A[j]] {14                     dp[i][j] = dp[j][k] + 115                     res = max(res,dp[i][j])16                 }17             }18         }19         return res20     }21 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode873. 最长的斐波那契子序列的长度 | Length of Longest Fibonacci Subsequence全部内容，希望文章能够帮你解决[Swift]LeetCode873. 最长的斐波那契子序列的长度 | Length of Longest Fibonacci Subsequence所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。