718. 最長(zhǎng)重復(fù)子數(shù)組

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
      解釋?zhuān)?      長(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)))
}