LeetCode/kt/length-of-longest-fibonacci-subsequence.kt

33 lines
769 B
Kotlin

class Solution {
fun lenLongestFibSubseq(arr: IntArray): Int {
val n = arr.size
val dp = Array(n) { IntArray(n) }
var maxLen = 0
(2..n - 1).forEach {
var (l, r) = 0 to it - 1
while (l < r) {
val sum = arr[l] + arr[r]
when {
sum > arr[it] -> r--
sum < arr[it] -> l++
else -> {
dp[r][it] = dp[l][r] + 1
maxLen = listOf(maxLen, dp[r][it]).max()!!
r--
l++
}
}
}
}
return when (maxLen) {
0 -> 0
else -> maxLen + 2
}
}
}