题目: 最大子数组和

方法一：穷举法

穷举法可以穷举任意两个位置的组合，计算这两个位置之间的子数组和。

算法流程

使用两层循环，

外层循环 i 表示子数组的开始位置，从0到 nums 的长度 -1 进行循环。

内层循环 j 表示子数组的结束位置，从 i + 1到 nums 的长度 -1 进行循环。

计算从 i 到 j 位置的数字之和。

将所有的组合中最大的和进行输出。

方法二：动态规划

如果知道一个子数组（i到j）的最大和，那么子数组 i 到 j+1 的最大和也可以确定，所以这个问题可以使用动态规划解决。

动态规划一般分为确定变量，确定状态转移方程，确定边界条件等三个步骤。

• 确定状态和状态变量
  • 分析问题特点，按照时间或者空间特征，将问题分为有序的若干阶段，因为动态规划是按顺序递推求解，所以阶段一定是可排序的。
  • 确定问题每个阶段求解时的状态，确定所需要的变量。求解过程一般是确定dp数组以及下标的含义。

• 确定状态转移方程
  • 分析决策过程，确定状态转移方程，决策和状态转移是相互联系的，状态是根据上一阶段状态以及当前决策变迁到当前状态的，所以确定决策就可以明确状态迁移方程，实际求解过程中，往往根据当前阶段和上一阶段的状态差异，推导决策过程。
• 确定边界条件
  • 状态转移方程是递推的过程，所以需要确定递推的边界条件。因为递推过程是从前到后依次执行的，所以边界条件一般就是初始值。

假设状态变量是结束位置，以结束位置 n 为数组最后一个位置的子数组的最大和是 f（n）。

当f（n）是正数的时候，f（n+1）= f（n）+ a_n+1，否则 f（n+1）= a_n+1。

边界条件是f（0）= a₀。

所以状态转移方程是：

$f(n)={\begin{cases}a_{0},&{\text{if }}n=0\\f(n-1)+a_{n},&{\text{if }}f(n-1)>=0\And n<{\text{a.length()}}\\a_{n}&{\text{if }}f(n-1)<0\And n<{\text{a.length()}}\end{cases}}$