LeetCode #1458. 두 개의 부분수열의 최대 내적

Source: Dev.to

Problem

두 배열 nums1과 nums2가 주어질 때, 길이가 같은 비어 있지 않은 부분수열들 사이의 최대 내적을 반환하세요.

배열의 부분수열은 남은 원소들의 상대적인 순서를 유지하면서 일부(또는 전혀) 원소를 삭제하여 만든 새로운 배열입니다.
예를 들어, [2,3,5]는 [1,2,3,4,5]의 부분수열이지만, [1,5,3]은 아닙니다.

Example 1

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: nums1에서 부분수열 [2,-2]를, nums2에서 부분수열 [3,-6]를 선택합니다. 이들의 내적은 2*3 + (-2)*(-6) = 18입니다.

Example 2

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: nums1에서 부분수열 [3]을, nums2에서 부분수열 [7]을 선택합니다. 이들의 내적은 3*7 = 21입니다.

Example 3

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: nums1에서 부분수열 [-1]을, nums2에서 부분수열 [1]을 선택합니다. 이들의 내적은 -1입니다.

Constraints

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

Discussion

이 문제는 최장 공통 부분수열(Longest Common Subsequence, LCS) 기법과 유사한 동적 프로그래밍으로 접근할 수 있습니다.
dp[i][j]가 nums1[0..i]와 nums2[0..j]의 접두사를 이용한 최대 내적을 저장하도록 2‑D DP 배열을 유지합니다.
각 쌍 (i, j)에 대해 다음을 고려합니다:

1. nums1[i] * nums2[j]를 곱해 이전 최적 부분수열을 연장하는 경우.
2. nums1[i] * nums2[j]만으로 새로운 부분수열을 시작하는 경우.
3. nums1[i]를 건너뛰는 경우 (dp[i‑1][j] 사용).
4. nums2[j]를 건너뛰는 경우 (dp[i][j‑1] 사용).

첫 번째 행과 첫 번째 열에 대해서는 비어 있지 않은 부분수열을 보장하기 위해 별도로 처리합니다.

Solution

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int firstRowMax = nums1[0] * nums2[0];
        dp[0][0] = firstRowMax;

        // Initialize first row
        for (int j = 1; j < nums2.length; j++) {
            int current = nums1[0] * nums2[j];
            firstRowMax = Math.max(firstRowMax, current);
            dp[0][j] = firstRowMax;
        }

        int answer = firstRowMax;

        // Fill the DP table
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int current = nums1[i] * nums2[j];
                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], current);
                } else {
                    dp[i][j] = Math.max(
                        dp[i - 1][j - 1] + current,
                        Math.max(
                            current,
                            Math.max(dp[i - 1][j], dp[i][j - 1])
                        )
                    );
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        return answer;
    }
}