ZBLOG

第一行输入连个整数n,sum 第二行输入n个整数的数组 你可以将其中一个数改为sum,求连续最大子数组最大和 请用golang实现

以下是使用golang实现该算法的示例代码:

package main

import (
	"fmt"
)

func maxSubArray(nums []int, sum int) int {
	maxSum := nums[0]
	currSum := 0
	left := 0
	right := -1

	for i := 0; i < len(nums); i++ {
		currSum += nums[i]

		if currSum == sum {
			left = 0
			right = i
			maxSum = currSum
			continue
		}

		if currSum-sum > maxSum {
			left = right + 1
			right = i
			maxSum = currSum - sum
		}

		if currSum < 0 {
			currSum = 0
		}
	}

	return sum + maxSum, left+1, right+1 // 返回最大和、子数组起始下标和结束下标(加1是为了符合题目要求)
}

func main() {
	var n, sum int
	fmt.Scan(&n)
	fmt.Scan(&sum)

	nums := make([]int, n)
	for i := range nums {
		fmt.Scan(&nums[i])
	}

	maxSubArrMaxSum, subArrStartIdx, subArrEndIdx := maxSubArray(nums, sum)

	fmt.Printf("连续最大子数组最大和: %d\n", maxSubArrMaxSum)
	fmt.Printf("起始下标: %d\n", subArrStartIdx)
	fmt.Printf("结束下标: %d\n", subArrEndIdx)
}

注意:上述代码假设输入的整数都不超过math.MaxInt32,如果需要处理更大的数字,应该使用更适合的数据类型。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=7068

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?