L53-Maximum-Subarray

题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解题思路

动态规划思想

以nums数组[-2,1,-3,4,-1]为例

dp[0]为-2
dp[1] = max(dp[0]+nums[1],1)=max(-2,1)=1
dp[2] = max(dp[1]+nums[2],-3)=max(1-3,-3)=-2
当前的sum为dp[i-1]+nums[i], nums[i]最大值
然后将maxSum和sum进行比较，取最大值

Go代码实现

Go代码实现1

func (a int, b int)int  {
	if a>b {
		return a
	}else{
		return b
	}
}
func maxSubArray(nums []int) int {
	n := len(nums)

	if n == 0 {
		return 0
	}

	if n == 1 {
		return nums[0]
大专栏  L53-Maximum-Subarrays="line">	}

	sums := make([]int, n)
	maxSum := nums[0]
	sums[0] = nums[0]

	for i:=1;i<n ; i++ {
		sums[i] = max(sums[i-1]+nums[i], nums[i])
		maxSum = max(sums[i], maxSum)
	}
	return maxSum
}

Go代码实现2

func maxSubArray(nums []int) int {
	n := len(nums)

	if n == 0 {
		return 0
	}

	maxSum := nums[0]
	curSum := nums[0]

	for i:=1;i<n ; i++ {
		if curSum<0 {
			curSum = nums[i]
		}else{
			curSum += nums[i]
		}

		if curSum>maxSum {
			maxSum = curSum
		}
	}
	return maxSum
}

参考文档

http://blog.csdn.net/liu2012huan/article/details/51296635

巴特西