LeetCode 1458. 两个子序列的最大点积

Categories:

题目描述
思路分析
1. 解法一：DP（推荐）
相似题目

题目描述

✅ 1458. 两个子序列的最大点积

思路分析

解法一：DP（推荐）

核心思路：

设 dp[i][j] 为 nums1[0..i) 与 nums2[0..j) 的最大点积。

转移包含：

选当前元素：nums1[i-1] * nums2[j-1] + max(0, dp[i-1][j-1])

或跳过一个元素：dp[i-1][j]、dp[i][j-1]

用负无穷初始化，保证至少选一对。

复杂度分析：

时间复杂度：O(n * m)。

空间复杂度：O(n * m)。

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];
        int negInf = -1_000_000_000;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = negInf;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int val = nums1[i - 1] * nums2[j - 1];
                dp[i][j] = Math.max(dp[i][j], val + Math.max(0, dp[i - 1][j - 1]));
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
}

func maxDotProduct(nums1 []int, nums2 []int) int {
    n := len(nums1)
    m := len(nums2)
    negInf := -1 << 60
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, m+1)
        for j := 0; j <= m; j++ {
            dp[i][j] = negInf
        }
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            val := nums1[i-1] * nums2[j-1]
            best := val
            if dp[i-1][j-1] > 0 {
                best = val + dp[i-1][j-1]
            }
            dp[i][j] = maxInt(dp[i][j], best)
            dp[i][j] = maxInt(dp[i][j], dp[i-1][j])
            dp[i][j] = maxInt(dp[i][j], dp[i][j-1])
        }
    }
    return dp[n][m]
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
1035. 不相交的线	中等	DP
1143. 最长公共子序列	中等	DP
718. 最长重复子数组	中等	DP
53. 最大子数组和	简单	DP
152. 乘积最大子数组	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/84268424