题目地址：

https://leetcode.com/problems/get-the-maximum-score/

给定两个严格递增数组$A$和$B$，一条合法路径的定义为： 1、可以从$A[0]$或者$B[0]$开始向右走； 2、如果走到了某个数$A[i]=B[j]$，可以转到另一个数组继续向右走。 一条合法路径的得分定义为该路径的数字和。如果中途转到另一个数组了，交叉点的那个数只算一次。问最大分数是多少。答案返回的时候要模一下$10^9+7$。

思路是动态规划。设$f[i]$是以$A[i]$为结尾的合法路径的最大得分（准确的说，是合法路径的到$A[i]$为止的这一段的最大得分），设$g[i]$是以$B[i]$为结尾的合法路径的最大得分。那么，如果$A[i]$不存在与$B$中，那么$f[i]=f[i-1]+A[i]$，同理如果$B[i]$不存在于$A$中，则$g[i]=g[i-1]+B[i]$。如果$A[i]=B[j]$，那么$$f[i]=g[j]=\max \{f[i-1],g[j-1]\}+A[i]$$我们发现，为了得到$f[i]$，不仅$f[0:i-1]$要算出来，所有小于$A[i]$的$B$对应的下标的$g$数组也都要算出来。由于数组是严格递增的，所以可以考虑用两个指针$i$和$j$，分别指向$A$和$B$，当$A[i]<B[j]$的时候更新$f[i]$，当$A[i]>B[j]$的时候更新$g[j]$，当$A[i]=B[j]$的时候同时更新$f[i]$和$g[j]$，这样就能达到效果。最后要返回的答案就是$\max \{f[l_A-1],g[l_B-1]\}$。代码如下：

public class Solution { public int maxSum(int[] nums1, int[] nums2) { int MOD = (int) (1e9 + 7); // 为了防止溢出，用long数组 long[] dp1 = new long[nums1.length], dp2 = new long[nums2.length]; int i = 0, j = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] < nums2[j]) { dp1[i] = ((i >= 1 ? dp1[i - 1] : 0) + nums1[i]); i++; } else if (nums1[i] > nums2[j]) { dp2[j] = ((j >= 1 ? dp2[j - 1] : 0) + nums2[j]); j++; } else { dp1[i] = dp2[j] = (Math.max(i >= 1 ? dp1[i - 1] : 0, j >= 1 ? dp2[j - 1] : 0) + nums1[i]); i++; j++; } } while (i < nums1.length) { dp1[i] = (i >= 1 ? dp1[i - 1] : 0) + nums1[i]; i++; } while (j < nums2.length) { dp2[j] = (j >= 1 ? dp2[j - 1] : 0) + nums2[j]; j++; } return (int) (Math.max(dp1[nums1.length - 1], dp2[nums2.length - 1]) % MOD); } }

时空复杂度$O(l_A+l_B)$。

考虑空间优化。我们可以只用两个变量做更新。代码如下：

public class Solution { public int maxSum(int[] nums1, int[] nums2) { int MOD = (int) (1e9 + 7); long dp1 = 0, dp2 = 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]) { dp1 += nums1[i++]; } else if (nums1[i] > nums2[j]) { dp2 += nums2[j++]; } else { dp1 = dp2 = Math.max(dp1, dp2) + nums1[i]; i++; j++; } } else if (i < nums1.length) { dp1 += nums1[i++]; } else { dp2 += nums2[j++]; } } return (int) (Math.max(dp1, dp2) % MOD); } }

时间复杂度不变，空间$O(1)$。