003.子数组

• 53.最大子数组和
  • 贪心
  • 动态规划
  • 分治

最大子数组和 - 贪心 §

func maxSubArray(nums []int) int {
	n := len(nums)
	if n == 0 {
		panic("input slice length is 0")
	}
 
	res := math.MinInt64
	cur := 0
	for _, v := range nums {
		cur += v
		res = max(res, cur)
		if cur < 0 {
			cur = 0
		}
	}
 
	return res
}

最大子数组和 - 动态规划 §

func maxSubArray(nums []int) int {
	n := len(nums)
	if n == 0 {
		panic("input slice length is 0")
	}
 
	dp := nums[0]
	res := dp
	for i := 1; i < n; i++ {
		dp = max(nums[i], dp + nums[i])
		res = max(res, dp)
	}
 
	return res
}

最大子数组和 - 分治 §

var (
	theNums []int
)
 
type Status struct {
	lSum int // [l,r] 内以 l 为左端点的最大子段和
	rSum int // [l,r] 内以 r 为左端点的最大子段和
	mSum int // [l,r] 内的最大子段和
	iSum int // [l,r] 的区间和
}
 
func maxSubArray(nums []int) int {
	n := len(nums)
	if n == 0 {
		panic("input slice length is 0")
	}
	theNums = nums
	return get(0, n - 1).mSum
}
 
func get(left, right int) Status {
	if left == right {
		return Status{
			lSum: theNums[left],
			rSum: theNums[left],
			mSum: theNums[left],
			iSum: theNums[left],
		}
	}
	mid := left + ((right - left) >> 1)
	lSub := get(left, mid)
	rSub := get(mid + 1, right)
	return pushUp(lSub, rSub)
}
 
func pushUp(left, right Status) Status {
	return Status{
		lSum: max(left.lSum, left.iSum + right.lSum),
		rSum: max(right.rSum, right.iSum + left.rSum),
		mSum: max(left.mSum, right.mSum, left.rSum + right.lSum),
		iSum: left.iSum + right.iSum,
	}
}