题目链接：https://leetcode.cn/problems/maximum-score-of-spliced-array/
思路
直接想法
1.这题表面是如何找子数组区间[Left:Right]使得对换之后，使其中一个的数组和最大。
2.但其实是在找两个数组之间[Left:Right]区间最大差值，差值我们自然而然的就可以想到差分，但是我们这里求的差分数组并不是两个数组前后元素的差值，而是两个数组同一下标的元素差值，这样我们只要找这段差分区间和的最大值就行了
算法
- 写一个solve方法，分别对两个数组进行找差分区间和最大值对比，求数组和最大值。
1. sum用来求数组之和
2. s 是找差分区间和，若差值 < 0 则重新找下一个差分区间
3. maxSum 是找差分区间和最大值
代码示例
GO代码
func max(a, b int) int { if a < b { return b } return a } func solve(nums1, nums2 []int) int { sum, maxSum, s := 0, 0, 0 for i := range nums1 { //求数组之和 sum += nums1[i] //求差分区间之和 s = max(s+nums2[i]-nums1[i], 0) //求差分区间之和最大值 maxSum = max(maxSum, s) } return sum + maxSum } func maximumsSplicedArray(nums1, nums2 []int) int { return max(solve(nums1, nums2), solve(nums2, nums1)) }
C++代码
class Solution { public: int solve(vector<int>& nums1, vector<int>& nums2){ int sum = 0, s = 0, maxSum = 0,n = nums1.size(); for(int i=0; i < n; i++){ sum += nums1[i]; s = max(s + nums2[i] - nums1[i], 0); maxSum = max(maxSum, s); } return sum + maxSum; } int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) { return max(solve(nums1, nums2), solve(nums2, nums1)); } };
复杂度分析
- 时间复杂度：O(n) 其中n表示数组长度，遍历数组所需要的时间为O(n)
- 空间复杂度：O(1) 没有额外的空间申请
