1. Problem

Given two arrays nums1 and nums2.
Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.
A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

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. 솔루션

방법1:dp

두 시퀀스 별칭 A, B

정의 상태:

dp[i][j]dp[i][j]dp[i][j]는 A의 전 iii숫자와 B의 전 jjj숫자로 구성할 수 있는 최대 점적화를 나타낸다.

사고 초기화:

dp [i] [j] = -3 I N F dp [i] [j] = -INF dp [i] [j] = -3 INF, 마이너스 계열이 존재하기 때문에 결과는 마이너스일 수 있습니다.

사고 상태 이동 방정식:

dp[i][j] = A[i] × B[j], A, B의 현재 두 개만 선택하고 다른 개수는 선택하지 않음

dp[i][j] = max(dp[i][j], dp[i-1][j]), B의 제jj개수

만 선택

dp[i][j] = max(dp[i][j], dp[i][j-1]), A의 ii 개수만 선택

dp[i][j] = max(dp[i][j], dp[i-1][j-1] + A[i] × B[j])에서 A, B의 현재 두 수와 앞에서 선택한 수로 구성된 가장 긴 점적과를 선택한다.

사고 출력: dp[n1][n2]dp[n1][n2]dp[n1][n2]

class Solution {
    public int maxDotProduct(int[] A, int[] B) {
    	int n1 = A.length, n2 = B.length, INF = -0x3f3f3f3f, f[][] = new int[n1+1][n2+1];
    	for (int i = 0; i <= n1; i++)
		for (int j = 0; j <= n2; j++)
			f[i][j] = INF;

		for (int i = 1 ; i <= n1; i++)
		for (int j = 1 ; j <= n2; j++) {
			int pro = A[i-1] * B[j-1];
			f[i][j] = pro;
			f[i][j] = Math.max(f[i][j], f[i][j-1]);
			f[i][j] = Math.max(f[i][j], f[i-1][j]);
			f[i][j] = Math.max(f[i][j], f[i-1][j-1] + pro);
		}
		return f[n1][n2];
    }
}

복잡도 분석

시간 복잡성: O(n 1× n 2 ) O(n1 × n2) O(n1×n2),

공간 복잡성: O(n 1× n 2 ) O(n1 × n2) O(n1×n2)