龙空技术网

leetcode2321_go_拼接数组的最大分数

每天都AC 226

前言:

此时我们对“c语言两个整数求最大值”大致比较看重,兄弟们都需要了解一些“c语言两个整数求最大值”的相关内容。那么小编在网络上汇集了一些有关“c语言两个整数求最大值””的相关知识,希望我们能喜欢,各位老铁们一起来学习一下吧!

题目

给你两个下标从 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、前缀和;时间复杂度O(n),空间复杂度O(1)

func maximumsSplicedArray(nums1 []int, nums2 []int) int {   return max(solve(nums1, nums2), solve(nums2, nums1)) // 取2种情况最大值}func solve(nums1 []int, nums2 []int) int {   maxDiff := 0   sum1 := 0   sum := 0   // nums1 + maxDiff(num2[left:right]-sum1[left:right])   // 求maxDiff最大   // 使用最大子序和来计算maxDiff   for i := 0; i < len(nums1); i++ {      sum1 = sum1 + nums1[i]      // leetcode 53.最大子序和      sum = max(0, sum+nums2[i]-nums1[i])      maxDiff = max(maxDiff, sum)   }   return sum1 + maxDiff}func max(a, b int) int {   if a > b {      return a   }   return b}
总结

Hard题目,题目可以转换为求leetcode53.最大自序和

标签: #c语言两个整数求最大值