最长重复子数组 ​

// 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

// 示例：

// 输入：

// A: [1,2,3,2,1]
// B: [3,2,1,4,7]
// 输出：3
// 解释：长度最长的公共子数组是 [3, 2, 1] 。

function fn(a, b){
    // dp[i][j] 代表i-1结尾的a与j-1结尾的b最长重复子数组
    // 初始化为0
    const alen = a.length, blen = b.length, dp = new Array(alen + 1).fill(0).map(() => new Array(blen + 1).fill(0))
    let res = 0
    for(let i = 1; i <= alen; i ++){
        for(let j = 1; j <= blen; j ++){
            if(a[i - 1] === b[j - 1]){
                // 递推公式：dp[i][j] = dp[i - 1][j - 1] + 1
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            res = Math.max(dp[i][j], res)
        }
    }
    console.table(dp);
    return res
}

console.log(fn([1,2,3,2,1], [3,2,1,4,7]))

// ┌─────────┬───┬───┬───┬───┬───┬───┐
// │ (index) │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │
// ├─────────┼───┼───┼───┼───┼───┼───┤
// │    0    │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
// │    1    │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │i:3,j=1; [1,2,3,2] | [3,2]  a[i-1] === b[j-1]; so => dp[3][1] = 1
// │    2    │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │i:2,j=2; [1,2,3] | [3,2,1]  a[i-1] === b[j-1]; so => dp[2][2] = 1
// │    3    │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │i:1,j=3; [1,2] | [3,2,1,4]  a[i-1] === b[j-1]; so => dp[1][3] = 1
// │    4    │ 0 │ 0 │ 2 │ 0 │ 0 │ 0 │
// │    5    │ 0 │ 0 │ 0 │ 3 │ 0 │ 0 │
// └─────────┴───┴───┴───┴───┴───┴───┘

// 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

// 示例：

// 输入：

// A: [1,2,3,2,1]
// B: [3,2,1,4,7]
// 输出：3
// 解释：长度最长的公共子数组是 [3, 2, 1] 。

function fn(a, b){
    // dp[i][j] 代表i-1结尾的a与j-1结尾的b最长重复子数组
    // 初始化为0
    const alen = a.length, blen = b.length, dp = new Array(alen + 1).fill(0).map(() => new Array(blen + 1).fill(0))
    let res = 0
    for(let i = 1; i <= alen; i ++){
        for(let j = 1; j <= blen; j ++){
            if(a[i - 1] === b[j - 1]){
                // 递推公式：dp[i][j] = dp[i - 1][j - 1] + 1
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            res = Math.max(dp[i][j], res)
        }
    }
    console.table(dp);
    return res
}

console.log(fn([1,2,3,2,1], [3,2,1,4,7]))

// ┌─────────┬───┬───┬───┬───┬───┬───┐
// │ (index) │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │
// ├─────────┼───┼───┼───┼───┼───┼───┤
// │    0    │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
// │    1    │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │i:3,j=1; [1,2,3,2] | [3,2]  a[i-1] === b[j-1]; so => dp[3][1] = 1
// │    2    │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │i:2,j=2; [1,2,3] | [3,2,1]  a[i-1] === b[j-1]; so => dp[2][2] = 1
// │    3    │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │i:1,j=3; [1,2] | [3,2,1,4]  a[i-1] === b[j-1]; so => dp[1][3] = 1
// │    4    │ 0 │ 0 │ 2 │ 0 │ 0 │ 0 │
// │    5    │ 0 │ 0 │ 0 │ 3 │ 0 │ 0 │
// └─────────┴───┴───┴───┴───┴───┴───┘