题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6 

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

构建模型：

我们定义一个数组dp[]，dp[i]是以第i个元素为结尾的一段最大子序和, 定义一个变量max为前i个元素的最大子序和。

寻找状态转移方程：

因为 max[ i ] 为前i个元素的最大子序和  ，所以max[i+1]等于 ：

1. 当 dp[ i+1]  > max[i]     ， max[i+1] =   dp[ i+1]

2. 当 dp[ i+1]  <=  max[i]  ,   max[i+1] =   max[i]

接下来我们论证一下 dp[i] 和 dp[i+1]的关系 （要不要加入到前面序列的尾部）：

1.  dp[i] <0 ： dp[i+1] = nums[i+1]

解释：如果将nums[i+1]加入到前面序列尾部那么新的序列最大值小于nums[i], 所以直接舍弃掉dp[i]序列， dp[i+1]仅包含 nums[i]  。

2.  dp[i] >=0 ： dp[i+i] = dp[i] + nums[i+1]

解释：将num[i+1] 加入到dp[i]的序列尾部。

所以max [i+1] 的最优解 我们是可以通过max[i] , dp[i]  来得到满足最优化原理。

代码实现如下：

func maxSub(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numsLen := len(nums)
	max := nums[0]
	dpTmp := nums[0]

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

		if dpTmp > max {
			max = dpTmp
		}
	}

	return max
}