题目描述

给定一个数组 A，找出此数组中，所有子数组中和最大的子数组，即为最大子数组问题。

动态规划逻辑

  • n-1 为原问题 n 的子问题
  • 求解改为：包含数组最后一个元素的最大子数组
  • 最大子数组问题的最优解的结构特征
    B[n] = B[n-a]Uxn
  • 找出最优解对应的最优值，并递归的定义最优值
1
2
3
4
b[n] = {
  b[n-1] + xn           b[n-1]>0;
  xn                    b[n-1]<=0;
}
  • 自底向上求解最优值