[LeetCode/JAVA] Max dot product of two subsequences

Problem

https://leetcode.com/problems/max-dot-product-of-two-subsequences/
두 개의 배열 nums1과 nums2가 주어진다.
비어 있지 않은 nums1과 nums2의 같은 길이를 가진 subsequences 사이의 내적 중 가장 큰 값을 반환한다.
subsequence는 배열에 속한 문자의 위치를 유지한 채로 문자의 일부를 삭제해 원래 배열에서 생성하는 새로운 배열이다.

Solution

• Dynamic Programming을 이용해 풀이할 수 있다.
• 먼저 nums1과 nums2의 길이를 이용해 2차원 dp 배열을 만든다.
• 2중 for문 안에서 nums1의 i번째 원소와 nums2의 j번째 원소의 곱을 구한다.
• dp[i][j]에서 구할 수 있는 최대값은 (i > 0 && j > 0)일 때 nums[i] * num[j] + Math.max(dp[i - 1][j - 1], 0) 이다. 곱의 결과가 음수일 수도 있기 때문에 0과 비교해 더 큰 값을 더해준다.
• dp[i][j]에서 새로 구한 값이 이전에 구한 값보다 작은 경우가 있을 수 있으므로 dp[i - 1][j] 혹은 dp[i][j - 1]와 dp[i][j]를 비교해 더 큰 값으로 업데이트한다.
• for문을 빠져나오면 dp의 마지막 요소가 subsequence 사이 내적의 최대값이다.

이미지로 보면 더 이해가 쉽다.

출처 : https://leetcode.com/problems/max-dot-product-of-two-subsequences/discuss/648528/Finally-a-diagram-to-make-understanding-easy

JAVA Code

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length, dp[][] = new int[len1][len2];
        
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                dp[i][j] = nums1[i] * nums2[j];
                if (i > 0 && j > 0) dp[i][j] += Math.max(dp[i - 1][j - 1], 0);
                if (i > 0) dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
                if (j > 0) dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
            }
        }
        return dp[len1 - 1][len2 - 1];
    }
}