42.md

连续子数组的最大和

题目

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求:时间复杂度为 O(n)，空间复杂度为 O(n) 进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

示例

输入：[1,-2,3,10,-4,7,2,-5]

返回值：18

说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

思路

• 状态定义：dp[i]表示以i结尾的连续子数组的最大和。所以最终要求dp[n-1]
• 状态转移方程：dp[i] = max(array[i], dp[i-1]+array[i])

但是这个公式怎么来的呢？

• 假设中间两个紧挨着的位置 m 和 n， m 在 n 的前边
• 假如 m 已经和前边元素都遍历相加对比过，知道了以 m 结尾的连续子数组的最大和 为 x
• 那么以 n 结尾的连续子数组的最大和就是 n + x 和 n 中的较大值
• 当知道了以数组中每个元素结尾的子数组的连续子数组的最大和后，再取其中最大的

实现

package main

// 连续子数组的最大和
func main() {
	data := []int{1, -2, 3, 10, -4, 7, 2, -5}
	FindGreatestSumOfSubArray(data)
}

func FindGreatestSumOfSubArray(array []int) int {
	size := len(array)
	dp := 0
	ret := array[0]
	for i := 1; i <= size; i++ {
		dp = max(array[i-1], dp+array[i-1])
		ret = max(ret, dp)
	}
	return ret
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}