题目描述

这是 LeetCode 上的 「1537. 最大得分」 ，难度为 「困难」。

Tag : 「前缀和」、「构造」、「双指针」、「序列 DP」、「动态规划」

你有两个 有序且数组内元素互不相同的数组nums1 和nums2。

一条合法路径定义如下：

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

得分定义为合法路径中不同数字的和。

请你返回所有可能合法路径中的最大得分。

由于答案可能很大，请你将它对 取余后返回。

示例 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

提示：

  • nums1 和 nums2都是严格递增的数组。

前缀和 + 构造（分段计算）

一个简单且正确的做法，是我们构造一种决策方案，使得能够直接计算出最大得分。

首先，在最佳路径中所有的公共点都必然会经过，因此我们可以将值相等的点进行合并，即看作同一个点。

利用两个数组均满足「单调递增」，我们可以通过 的复杂度统计出那些公共点，以二元组 的形式存储到 list 数组（二元组含义为 ）。

对于 list 中的每对相邻元素（相邻公共点），假设为 和 ，我们可以通过「前缀和」计算出 以及 的和，从而决策出在 （或者说是 ，这两个是同一个点）时，我们应当走哪一段。

当计算完所有公共点之间的得分后，对于最佳路线的首位两端，也是结合「前缀和」做同样的逻辑处理即可。

代码：

classSolution{
intMOD=(int)1e9+7;
publicintmaxSum(int[]nums1,int[]nums2){
intn=nums1.length,m=nums2.length;
long[]s1=newlong[n+10],s2=newlong[m+10];
for(inti=1;i<=n;i++)s1[i]=s1[i-1]+nums1[i-1];
for(inti=1;i<=m;i++)s2[i]=s2[i-1]+nums2[i-1];
List<int[]>list=newArrayList();
for(inti=0,j=0;i<n&&j<m;){
if(nums1[i]==nums2[j])list.add(newint[]{i,j});
if(nums1[i]<nums2[j])i++;
elsej++;
}
longans=0;
for(inti=0,p1=-1,p2=-1;i<=list.size();i++){
intidx1=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;
}
longt1=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);
}
}
  • 时间复杂度：
  • 空间复杂度：

序列 DP

另外一个较为常见的做法是「序列 DP」做法。

定义 代表在 nums1 上进行移动，到达 的最大得分；定义 代表在 nums2 上进行移动，到达 的最大得分。

由于两者的分析是类似的，我们以 为例进行分析即可。

不失一般性考虑 如何转移，假设当前处理到的是 ，根据 是否为公共点，进行分情况讨论：

  • 不为公共点，此时只能由 转移而来，即有 ；
  • 为公共点（假设与 公共），此时能够从 或 转移而来，我们需要取 和 的最大值，即有 。

更重要的是，我们需要确保计算 时， 已被计算完成。

由于最佳路线必然满足「单调递增」，因此我们可以使用「双指针」来对 和 同时进行转移，每次取值小的进行更新，从而确保更新过程也是单调的，即当需要计算 时，比 小的 和 均被转移完成。

代码：

classSolution{
intMOD=(int)1e9+7;
publicintmaxSum(int[]nums1,int[]nums2){
intn=nums1.length,m=nums2.length;
long[]f=newlong[n+1],g=newlong[m+1];
inti=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++;
}elseif(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++;
}
}elseif(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);
}
}
  • 时间复杂度：
  • 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1537 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关的资料可访问排版精明的 合集新基地

本文由 mdnice 多平台发布