1537. Get the Maximum Score¶
题目信息¶
- 题号:
1537
- 难度:
Hard
- 主题:
有序数组、双指针、动态规划
- 原题:
- 重点:
沿一个严格递增数组前进,在两个数组的公共值处可以切换;公共值只能计分一次
题目重述¶
给定两个严格递增的正整数数组 nums1 和 nums2。可以从任一数组开头开始向右移动,并累加经过的元素。
当当前位置的数值同时出现在另一个数组中时,可以继续留在当前数组,也可以从该公共值切换到另一个数组;公共值只加入总分一次。请返回可获得的最大总分对 10^9 + 7 取模后的结果。
两个数组长度均不超过 10^5,元素为正整数且各数组内部严格递增。
自建示例¶
每个公共值之间可以选择分数更高的一侧:
输入:nums1 = [1,3,5,7], nums2 = [1,2,5,8]
输出:17
解释:依次选择公共值 1、区间中的 3、公共值 5,以及末段的 8,总分为 17。
没有公共值时只能完整选择其中一个数组:
输入:nums1 = [1,2], nums2 = [4]
输出:4
解释:两条路径不能切换,第二个数组总和更大。