leetcode-2321. 拼接数组的最大分数（差分+枚举）

题目链接：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) 没有额外的空间申请