算法基础——动态规划之最大子数组问题

• 问题描述
  
  - 分而治之的解决方案

  在分治算法中，已经学习过最大子数组问题。使用分治的方法：将大数组arr分为两个小数组arr_left和arr_right，则求解arr的最大子数组和等价于：

  在arr_left的最大子数组和、arr_right的最大子数组和、跨中点的最大子数组和中找一个最大的，即为arr的最大子数组和。

  采用分治算法解决该问题，Golang实现在前面分治的博客里写过，其时间复杂度为O(nlogn)，而使用dp的方法可以使复杂度降低至O(n)

• DP的解决方案

  1）分析问题结构： dp的第一步为分析问题结构，找到该问题的最佳子结构性质：对n个元素的数组arr[n]求解最大子数组和maxSum(n), 首先去找 maxSum(n) 和 maxSum(n-1) 的关系。

  假设我们已经知道前n-1个元素的最大子数组和 maxSum(n-1), 设前n个元素中以第n元素结尾的最大子数组和为 P(n) , 则

  maxSum(n) = max{ maxSum(n-1), P(n) }

  继续观察 P(n) 和 P(n-1) 的关系： 若以第n-1个元素结尾的最大子数组和 P(n-1) 加上第n个元素的和大于第n个元素(即P(n-1)>0)，那么以第n个元素结尾的最大子数组和为 P(n) = P(n-1) + arr[n]，否则 P(n) 就等于arrr[n] 第n个元素本身， 即：

  P(n) = max{ P(n-1)+arr[n], arr[n] }

  我们已经找到了maxSum(n)和maxSum(n-1)子问题的关系，这就是最大子数组和问题的最优子结构性质。

  2）构造递推式： 我们通过分析最优子结构性质。已经得到了dp的递推式：

  P(n) = max{ P(n-1)+arr[n], arr[n] }
  maxSum(n) = max{ maxSum(n-1), P(n) }

  3）初始化数组，自底向上求解： 构造两个一维数组 maxSum 和 P ; P[i]: 数组前i的元素中包含元素i的最大子数组和； maxSum[i]: 数组前i个元素中的最大子数组和。

  设没有元素的数组最大子数组和为负无穷以便于求解，即初始化P[0] 和maxSum[0] 为负无穷，而后以 i := 1 to n，自底向上求解，得到 **maxSum[n]**的值即为最大子数组和

  Golang实现如下：

const negInfinity  = -1000 //负无穷

func Max(s1 int, s2 int) int {
	max := s1
	if s2 > max {
		max = s2
	}

	return max
}

func MaxSum(arr []int) int {

	lenx := len(arr) //数组长度

	//构造dp表
	pTable := make([]int, lenx) //pTable[i]表示前i个元素组成的数组的最大子数组和
	qTable := make([]int, lenx) //qTable[i]表示前i的元素中包含第i个元素的最大子数组和

	//初始化dp Table
	pTable[0] = negInfinity
	qTable[0] = negInfinity

	for i:=1; i<lenx; i++ {
		qTable[i] = Max(qTable[i-1]+arr[i], arr[i])
		pTable[i] = Max(pTable[i-1], qTable[i])
	}

	return pTable[lenx-1]
}

func main() {
	
	//实际求解数组为{1,-2,4,5,-2,8,3,-2,6,3,7,-1}, 因数组下标从0算起，因此在下标0处随便填一个元素(0)占位
	arr4 := []int{0,1,-2,4,5,-2,8,3,-2,6,3,7,-1}
	maxSum := MaxSum(arr4)
	fmt.Println("MaxSum Result: ")
	fmt.Println("最大子数组和为", maxSum)
}