最大点积子序列

题目描述

给你两个整数数组 $nums1$ 和 $nums2$。请你在两个数组中分别选择长度相同且非空的子序列，使它们的点积最大。

数组的子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。

点积定义为：

若选择的子序列分别为 $a_1,a_2,\dots,a_k$ 与 $b_1,b_2,\dots,b_k$，则点积为

$$\sum_{i=1}^{k} a_i \cdot b_i.$$

请输出最大点积。

输入格式

输入共三行。

• 第一行包含两个整数 $n,m$，表示 $nums1$ 与 $nums2$ 的长度。
• 第二行包含 $n$ 个整数，表示 $nums1$。
• 第三行包含 $m$ 个整数，表示 $nums2$。

输出格式

输出一行，一个整数，表示最大点积。

输入输出样例 #1

输入 #1

4 3
2 1 -2 5
3 0 -6

输出 #1

18

样例解释 #1

可选子序列为 nums1 中的 [2,-2] 与 nums2 中的 [3,-6]，点积为 $2\cdot3 + (-2)\cdot(-6)=18$。

输入输出样例 #2

输入 #2

2 3
3 -2
2 -6 7

输出 #2

21

样例解释 #2

可选子序列为 nums1 中的 [3] 与 nums2 中的 [7]，点积为 $21$。

输入输出样例 #3

输入 #3

2 2
-1 -1
1 1

输出 #3

-1

样例解释 #3

可选子序列为 nums1 中的 [-1] 与 nums2 中的 [1]，点积为 $-1$。

数据范围

对于所有测试数据，保证：

• $1 \le n,m \le 500$；
• $-1000 \le nums1[i], nums2[j] \le 1000$。