每日一题：最大得分

题意

给定两个严格递增数组，从任意一个数组出发到任意一个数组结束，当遇到相同元素时可以切换到另一个数组，只能从左到右走且每个数只计算一次，求最大累计得分。

Solution

当遇到两个数组都有的元素时可以切换，那其实从上一次遇到相同到这一次，假设中间这部分元素和是 $sum$，无非是看到底是上面这部分的 $sum$ 更大还是下面的 $sum$ 更大，然后选走罢了，如此循环下去。至于判断相同元素，提前用map记录每个元素的位置就好了。时间复杂度$O(n)$。

比如:

$nums1: [2, 4, 5, 8, 10]$

$nums2: [4, 6, 8, 9]$

首先第一部分（从起点开始，碰到第一次相同）是 $sum1(nums1[2, 4]) = 6$, $sum2(nums2[4]) = 4$，选择 $max(sum1, sum2) = 6$

第二部分（第二次相同）是 $sum1(nums1[5, 8]) = 13$, $sum2(nums2[6, 8]) = 14$，选择 $max(sum1, sum2) = 14$

第三部分（一直循环到结尾也没再发现相同元素，换不了路线，故只能一直走到终点）是 $sum1(nums1[10]) = 10$, $sum2(nums2[9]) = 9$，选择 $max(sum1, sum2) = 10$

故答案为 $6 + 14 + 10 = 20$

Code

class Solution {
    public int maxSum(int[] a, int[] b) {
        int n = a.length, m = b.length;
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for(int i = 0; i < m; i++)
            mp.put(b[i], i);  // 预处理b[i]数组的位置
        long res = 0, sum1 = 0, sum2 = 0, mod = 1000000007;
        int j = 0;
        for(int i = 0; i < n; i++) {
            sum1 += a[i];  // 计算a数组这部分的和
            if(mp.get(a[i]) != null) {  // 说明a[i]在b数组中也存在
                int pos = mp.get(a[i]);
                for(; j <= pos; j++) {  // 开始计算b数组这部分的和
                    sum2 += b[j];
                }
                res = (res + Math.max(sum1, sum2)) % mod;  // 选择更大的那部分加
                sum1 = sum2 = 0;  // 归零，开始下一部分的计算
            }
        }
        for(; j < m; j++) {  // b数组可能还没走完
            sum2 += b[j];
        }
        res = (res + Math.max(sum1, sum2)) % mod;
        return (int)(res % 1000000007);
    }
}