2つのサブシーケンスの最大内積

Max Dot Product Two Subsequences

与えられた2つの配列nums1およびnums2。

間の最大内積を返します 空ではない 同じ長さのnums1とnums2のサブシーケンス。

配列のサブシーケンスは、残りの文字の相対位置を乱すことなく、文字の一部を削除することによって元の配列から形成される新しい配列です。 （つまり、[2,3,5]は[1,2,3,4,5]のサブシーケンスですが、[1,5,3]はそうではありません）。

例1：

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6] Output: 18 Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2. Their dot product is (2*3 + (-2)*(-6)) = 18.

例2：

Input: nums1 = [3,-2], nums2 = [2,-6,7] Output: 21 Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2. Their dot product is (3*7) = 21.

アイデア：dpの物理的な意味は次のとおりです：nums1からi、nums2からj、私が得ることができる最大のドットの合計

再帰は5つのケースに分けられます：nums1 [i] nums [j]は分割され、実行されません。

dp [i] [j] =

1は2を取り、2つのケースに分けられます。1と2のnums [i] * nums [j]のみが必要であるか、前のdp [i-1] [j-1] + nums1 [i] *も必要です。 nums [j]

1は取られない2が取られる、dp [i-1] [j]

1が取られ、2が取られない、dp [i] [j-1]

1は取られない、2は取られない、dp [i-1] [j-1]

すべての場合において、最大のものは現在最大のものです

初期値：0、0 nums1 [i] * nums [j]

1行目：現在の最大値を取得します

1列目：現在の最大値を取得します

class Solution { public int maxDotProduct(int[] nums1, int[] nums2) { int n = nums1.length int m = nums2.length long[][] dp = new long[n][m] long res = Long.MIN_VALUE for(int i = 0 i = 0) { dp[i][j] = Math.max(dp[i - 1][j], nums1[i] * nums2[j]) } else { // i >= 1 && j >= 1 dp[i][j] = Math.max(dp[i][j], nums1[i] * nums2[j]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + nums1[i] * nums2[j]) dp[i][j] = Math.max(dp[i][j], Math.max(dp[i - 1][j -1], Math.max(dp[i - 1][j], dp[i][j -1]))) } res = Math.max(res, dp[i][j]) } } return (int)res } }