golang刷leetcode：拼接数组的最大分数

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。

你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。

• 例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。

你可以选择执行上述操作 一次 或不执行任何操作。

数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。

返回 可能的最大分数 。

子数组 是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。

示例 1：

输入：nums1 = [60,60,60], nums2 = [10,90,10]输出：210解释：选择 left = 1 和 right = 1 ，得到 nums1 = [60,90,60] 和 nums2 = [10,60,10] 。
分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210 。

复制

示例 2：

输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]输出：220解释：选择 left = 3 和 right = 4 ，得到 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30] 。
分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220 。

复制

示例 3：

输入：nums1 = [7,11,13], nums2 = [1,1,1]输出：31解释：选择不交换任何子数组。
分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31 。

复制

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 104

解题思路：

1，本题可以转化为连续最小和和连续最大和问题

2，求数组nums1和nums2的差值diff=nums2-nums1

3，假设diff的最大连续和为maxdiff，最小连续和为mindiff

4,最大值一定在sum(nums1),sum(nums2),sum2(nums1)+maxdiff,sum(nums2)-mindiff中取

5，最大连续和怎么求呢，对于位置i，我们可以记录以i结尾的最大连续和为end[i],全局最大连续和为all[i]

6,有end[i]=max(end[i-1]+diff[i],diff[i]);all[i]=max(all[i-1],end[i])

7,初始条件all[i]=end[i]=diff[i]

代码实现

func maximumsSplicedArray(nums1 []int, nums2 []int) int {
    sum1:=0
    sum2:=0
    diff:=make([]int,len(nums1))
    for i:=0;i<len(nums1);i++{
        sum1+=nums1[i]
        sum2+=nums2[i]
       diff[i]=nums2[i]-nums1[i]
    }
    maxdiff:=getMaxMin(diff,true)
    mindiff:=getMaxMin(diff,false)
    return max(sum1,sum1+maxdiff,sum2,sum2-mindiff)
}

func max(a ...int)int{
    v:=a[0]
    for i:=1;i<len(a);i++{
        if a[i]>v{
            v=a[i]
        }
    }
    return v
}

func getMaxMin(diff []int,gt bool)int{
    all:=make([]int,len(diff))
    end:=make([]int,len(diff))
    end[0]=diff[0]
    all[0]=diff[0]
    for i:=1;i<len(diff);i++{
        end[i]=maxmin(diff[i],end[i-1]+diff[i],gt)
        all[i]=maxmin(end[i],all[i-1],gt)
    }
     //fmt.Println(diff,end, all)
    return all[len(diff)-1]
}

func maxmin(a,b int, gt bool)int{
    if gt{
        if a>b{
            return a
        }
        return b
        
    }
    if a>b{
        return b
    }
    return a
}

复制

由于只用到了i-1位置，因此可以降维

func maximumsSplicedArray(nums1 []int, nums2 []int) int {
    sum1:=0
    sum2:=0
    diff:=make([]int,len(nums1))
    for i:=0;i<len(nums1);i++{
        sum1+=nums1[i]
        sum2+=nums2[i]
       diff[i]=nums2[i]-nums1[i]
    }
    
    maxdiff:=getMaxMin(diff,true)
    mindiff:=getMaxMin(diff,false)


    return max(sum1,sum1+maxdiff,sum2,sum2-mindiff)
}

func max(a ...int)int{
    v:=a[0]
    for i:=1;i<len(a);i++{
        if a[i]>v{
            v=a[i]
        }
    }
    return v
}

func getMaxMin(diff []int,gt bool)int{
    end0:=diff[0]
    all0:=diff[0]
    for i:=1;i<len(diff);i++{
       end0=maxmin(diff[i],end0+diff[i],gt)
       all0=maxmin(end0,all0,gt)
        
    }
     //fmt.Println(diff,end, all)
    return all0
}

func maxmin(a,b int, gt bool)int{
    if gt{
        if a>b{
            return a
        }
        return b
        
    }
    if a>b{
        return b
    }
    return a
}

复制