数组
动态规划
题目描述
给你两个数组 nums1
和 nums2
。
请你返回 nums1
和 nums2
中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。比方说,[2,3,5]
是 [1,2,3,4,5]
的一个子序列而 [1,5,3]
不是。
示例 1:
输入: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出: 18
解释: 从 nums1 中得到子序列 [2,-2] ,从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。
示例 2:
输入: nums1 = [3,-2], nums2 = [2,-6,7]
输出: 21
解释: 从 nums1 中得到子序列 [3] ,从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。
示例 3:
输入: nums1 = [-1,-1], nums2 = [1,1]
输出: -1
解释: 从 nums1 中得到子序列 [-1] ,从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。
提示:
1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 100
点积:
定义 a = [a 1 , a 2 ,…, a n ] 和 b = [b 1 , b 2 ,…, b n ] 的点积为:
这里的 Σ 指示总和符号。
解法
方法一:动态规划
定义 $dp[i][j]$ 表示 $nums1$ 前 $i$ 个元素和 $nums2$ 前 $j$ 个元素得到的最大点积。
那么有:
$$
dp[i][j]=max(dp[i-1][j], dp[i][j - 1], max(dp[i - 1][j - 1], 0) + nums1[i] \times nums2[j])
$$
答案为 $dp[m][n]$。
时间复杂度 $O(m \times n)$,空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是数组 $nums1$ 和 $nums2$ 的长度。
Python3 Java C++ Go Rust
class Solution :
def maxDotProduct ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int :
m , n = len ( nums1 ), len ( nums2 )
dp = [[ - inf ] * ( n + 1 ) for _ in range ( m + 1 )]
for i in range ( 1 , m + 1 ):
for j in range ( 1 , n + 1 ):
v = nums1 [ i - 1 ] * nums2 [ j - 1 ]
dp [ i ][ j ] = max ( dp [ i - 1 ][ j ], dp [ i ][ j - 1 ], max ( dp [ i - 1 ][ j - 1 ], 0 ) + v )
return dp [ - 1 ][ - 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public int maxDotProduct ( int [] nums1 , int [] nums2 ) {
int m = nums1 . length , n = nums2 . length ;
int [][] dp = new int [ m + 1 ][ n + 1 ] ;
for ( int [] e : dp ) {
Arrays . fill ( e , Integer . MIN_VALUE );
}
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
dp [ i ][ j ] = Math . max ( dp [ i - 1 ][ j ] , dp [ i ][ j - 1 ] );
dp [ i ][ j ] = Math . max (
dp [ i ][ j ] , Math . max ( 0 , dp [ i - 1 ][ j - 1 ] ) + nums1 [ i - 1 ] * nums2 [ j - 1 ] );
}
}
return dp [ m ][ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int maxDotProduct ( vector < int >& nums1 , vector < int >& nums2 ) {
int m = nums1 . size (), n = nums2 . size ();
vector < vector < int >> dp ( m + 1 , vector < int > ( n + 1 , INT_MIN ));
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
int v = nums1 [ i - 1 ] * nums2 [ j - 1 ];
dp [ i ][ j ] = max ( dp [ i - 1 ][ j ], dp [ i ][ j - 1 ]);
dp [ i ][ j ] = max ( dp [ i ][ j ], max ( 0 , dp [ i - 1 ][ j - 1 ]) + v );
}
}
return dp [ m ][ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 func maxDotProduct ( nums1 [] int , nums2 [] int ) int {
m , n := len ( nums1 ), len ( nums2 )
dp := make ([][] int , m + 1 )
for i := range dp {
dp [ i ] = make ([] int , n + 1 )
for j := range dp [ i ] {
dp [ i ][ j ] = math . MinInt32
}
}
for i := 1 ; i <= m ; i ++ {
for j := 1 ; j <= n ; j ++ {
v := nums1 [ i - 1 ] * nums2 [ j - 1 ]
dp [ i ][ j ] = max ( dp [ i - 1 ][ j ], dp [ i ][ j - 1 ])
dp [ i ][ j ] = max ( dp [ i ][ j ], max ( 0 , dp [ i - 1 ][ j - 1 ]) + v )
}
}
return dp [ m ][ n ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 impl Solution {
#[allow(dead_code)]
pub fn max_dot_product ( nums1 : Vec < i32 > , nums2 : Vec < i32 > ) -> i32 {
let n = nums1 . len ();
let m = nums2 . len ();
let mut dp = vec! [ vec! [ i32 :: MIN ; m + 1 ]; n + 1 ];
// Begin the actual dp process
for i in 1 ..= n {
for j in 1 ..= m {
dp [ i ][ j ] = std :: cmp :: max (
std :: cmp :: max ( dp [ i - 1 ][ j ], dp [ i ][ j - 1 ]),
std :: cmp :: max ( dp [ i - 1 ][ j - 1 ], 0 ) + nums1 [ i - 1 ] * nums2 [ j - 1 ]
);
}
}
dp [ n ][ m ]
}
}
GitHub