共计 3256 个字符，预计需要花费 9 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 1537. 最大得分 ，难度为 艰难。
Tag :「前缀和」、「结构」、「双指针」、「序列 DP」、「动静布局」
你有两个 有序 且数组内元素互不雷同的数组 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都是严格递增的数组。
前缀和 + 结构（分段计算）
一个简略且正确的做法，是咱们结构一种决策计划，使得可能间接计算出最大得分。
首先，在最佳门路中所有的公共点都必然会通过，因而咱们能够将值相等的点进行合并，即看作同一个点。
利用两个数组均满足「枯燥递增」，咱们能够通过 $O(n + m)$ 的复杂度统计出那些公共点，以二元组 $(i, j)$ 的模式存储到 list 数组（二元组含意为 $nums1[i] = nums2[j]$）。
对于 list 中的每对相邻元素（相邻公共点），假如为 $(a_i, b_i)$ 和 $(c_i, d_i)$，咱们能够通过「前缀和」计算出 $nums1[a_i … c_i]$ 以及 $nums2[b_i … d_i]$ 的和，从而决策出在 $nums1[a_i]$（或者说是 $nums2[b_i]$，这两个是同一个点）时，咱们该当走哪一段。
当计算完所有公共点之间的得分后，对于最佳路线的首位两端，也是联合「前缀和」做同样的逻辑解决即可。
代码：
class Solution {int MOD = (int)1e9 + 7;
public int maxSum(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
long[] s1 = new long[n + 10], s2 = new long[m + 10];
for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + nums1[i - 1];
for (int i = 1; i <= m; i++) s2[i] = s2[i - 1] + nums2[i - 1];
List<int[]> list = new ArrayList<>();
for (int i = 0, j = 0; i < n && j < m;) {if (nums1[i] == nums2[j]) list.add(new int[]{i, j});
if (nums1[i] < nums2[j]) i++;
else j++;
}
long ans = 0;
for (int i = 0, p1 = -1, p2 = -1; i <= list.size(); i++) {
int idx1 = 0, idx2 = 0;
if (i < list.size()) {int[] info = list.get(i);
idx1 = info[0]; idx2 = info[1];
} else {idx1 = n - 1; idx2 = m - 1;}
long t1 = s1[idx1 + 1] - s1[p1 + 1], t2 = s2[idx2 + 1] - s2[p2 + 1];
ans += Math.max(t1, t2);
p1 = idx1; p2 = idx2;
}
return (int)(ans % MOD);
}
}- 工夫复杂度：$O(n + m)$
- 空间复杂度：$O(n + m)$
序列 DP
另外一个较为常见的做法是「序列 DP」做法。
定义 $f[i]$ 代表在 nums1 上进行挪动，达到 $nums1[i]$ 的最大得分；定义 $g[j]$ 代表在 nums2 上进行挪动，达到 $nums[j]$ 的最大得分。
因为两者的剖析是相似的，咱们以 $f[i]$ 为例进行剖析即可。
不失一般性思考 $f[i]$ 如何转移，假如以后解决到的是 $nums1[i]$，依据 $nums1[i]$ 是否为公共点，进行分状况探讨：
- $nums1[i]$ 不为公共点，此时只能由 $nums[i – 1]$ 转移而来，即有 $f[i] = f[i – 1] + nums[i]$；
- $nums1[i]$ 为公共点（假如与 $nums2[j]$ 公共），此时可能从 $nums1[i – 1]$ 或 $nums2[j – 1]$ 转移而来，咱们须要取 $f[i – 1]$ 和 $g[j – 1]$ 的最大值，即有 $f[i] = g[j] = \max(f[i – 1], g[j – 1]) + nums1[i]$。
更重要的是，咱们须要确保计算 $f[i]$ 时，$g[j – 1]$ 已被计算实现。
因为最佳路线必然满足「枯燥递增」，因而咱们能够应用「双指针」来对 $f[i]$ 和 $g[j]$ 同时进行转移，每次取值小的进行更新，从而确保更新过程也是枯燥的，即当须要计算 $f[i]$ 时，比 $nums1[i]$ 小的 $f[X]$ 和 $g[X]$ 均被转移实现。
代码：
class Solution {int MOD = (int)1e9 + 7;
public int maxSum(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
long[] f = new long[n + 1], g = new long[m + 1];
int i = 1, j = 1;
while (i <= n || j <= m) {if (i <= n && j <= m) {if (nums1[i - 1] < nums2[j - 1]) {f[i] = f[i - 1] + nums1[i - 1];
i++;
} else if (nums2[j - 1] < nums1[i - 1]) {g[j] = g[j - 1] + nums2[j - 1];
j++;
} else {f[i] = g[j] = Math.max(f[i - 1], g[j - 1]) + nums1[i - 1];
i++; j++;
}
} else if (i <= n) {f[i] = f[i - 1] + nums1[i - 1];
i++;
} else {g[j] = g[j - 1] + nums2[j - 1];
j++;
}
}
return (int) (Math.max(f[n], g[m]) % MOD);
}
}- 工夫复杂度：$O(n + m)$
- 空间复杂度：$O(n + m)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1537 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干的材料可拜访排版精明的 合集新基地 🎉🎉
本文由 mdnice 多平台公布