import kotlin.math.max
class FindLength {
/*
* 給兩個(gè)整數(shù)數(shù)組 A 和 B 颊郎，返回兩個(gè)數(shù)組中公共的辆脸、長(zhǎng)度最長(zhǎng)的子數(shù)組的長(zhǎng)度沧竟。
示例：
輸入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出：3
解釋：
長(zhǎng)度最長(zhǎng)的公共子數(shù)組是 [3, 2, 1] 焙压。
* */
/*
* 動(dòng)態(tài)規(guī)劃 另一種思路是滑動(dòng)窗口 也比較簡(jiǎn)單
* dp方程
* 如果當(dāng)前i和j對(duì)應(yīng)的數(shù)相等 則結(jié)果等于前一個(gè)結(jié)果+1 否則為0
* */
fun findLength(A: IntArray, B: IntArray): Int {
var dp = Array(A.size) { IntArray(B.size) }
var maxAns = 0
for (a in A.withIndex()) {
for (b in B.withIndex()) {
if (a.value == b.value) {
//結(jié)尾一樣 則前一個(gè)+1
if (a.index > 0 && b.index > 0) {
dp[a.index][b.index] = dp[a.index - 1][b.index - 1] + 1
} else {
dp[a.index][b.index] = 1
}
maxAns = max(maxAns, dp[a.index][b.index]);
} else {
dp[a.index][b.index] = 0
}
}
}
return maxAns
}
}
fun main() {
println(FindLength().findLength(intArrayOf(1,2,3,2,1), intArrayOf(3,2,1,4,7)))
}
