33 lines
769 B
Kotlin
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
|
|
}
|
|
}
|
|
}
|