leetcode1537. 最大得分(动态规划-java)_你有两个有序且数组内元素互不相同

题目描述

难度 - 困难
leetcode1537. 最大得分

你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下：

选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
从左到右遍历当前数组。
如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。

得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

示例1：
输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

示例 2：
输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

示例 3：
输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。

示例 4：
输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
输出：61

提示：
1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 和 nums2 都是严格递增的数组。

动态规划

这道题，我们最终是要合并出一条逻辑上的最大直线，因此遇到相同值时，我们就面临选择，因此我们可以用动态规划去解决：
我们用f(i) 和 g(j) 来分别表示遍历到数组 nums1[i]和 nums2[j]时的最大得分。如果遍历到的元素没有合并，那么它只会从相同数组的前一个元素转移而来：
f(i) = f(i - 1) + nums[i];
g(j) = g(j - 1) + nums2[j];

如果遍历到元素相等，那么就需要合并了。例如 nums1[i]=nums2[j]，那么它可以从任意一个数组中对应位置的前一个元素转移而来，我们选择其中的较大值：
f[i]=g[j]=max(f[i−1],g[j−1])+nums1​[i]

最终的答案即为 f[m−1]f[m-1]f[m−1] 与 g[n−1]g[n-1]g[n−1] 中的较大值

下面就要讨论，状态如何转移：
因为两个数组都是有序而且单调递增的。因此我们可以用双指针分别卡住两个数组的两端，从左向右去遍历去做选择。
1.使用两个指针 i 和 j 分别指向数组 nums1​ 和 nums2​ 的首元素；
2.每次在进行状态转移前，比较 nums1[i]] 的 nums2[j] 的大小关系。如果前者较小，那么对前者进行状态转移：
f[i]=f[i−1]+nums1​[i]
如果后者较小，那么对后者进行状态转移：
g[j]=g[j−1]+nums2​[j]
如果两者相等，那么同时进行状态转移：
f[i]=g[j]=max(f[i−1],g[j−1])+nums1​[i]

这样一来，我们就可以顺利地完成动态规划并得到答案。注意到在进行状态转移时，f[i]和 g[j]] 只会从 f[i−1 和 g[j−1] 转移而来，因此我们并不需要使用两个一维数组来存放动态规划的结果。我们可以仅使用两个变量 best1​ 和 best2 进行转移：
best1=best1+nums1[i]
best2=best2+nums2[j]
best1=best2=max⁡(best1,best2)+nums1[i]
它们的初始值均为 0。

代码演示

class Solution {
   
    public int maxSum(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        long best1 = 0;
        long best2 = 0;
        //双指针
        int i = 0,j = 0;
        while(i < nums1.length || j < nums2.length){
            if(i < nums1.length && j < nums2.length){
                if(nums1[i] < nums2[j]){
                    best1 += nums1[i++];
                }else if(nums1[i] > nums2[j]){
                    best2 += nums2[j++];
                }else{
                    long best = Math.max(best1,best2) + nums1[i];
                    best1 = best;
                    best2 = best;
                    i++;
                    j++;
                }
            }else if(i < nums1.length){
                best1 += nums1[i++];
            }else if(j < nums2.length){
                best2 += nums2[j++];
            }
        }

        return (int)(Math.max(best1,best2) % MOD);
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33