转自出处：http://likecer.com/dp-biggest-sub/

动态规划是种神奇的算法，最开始学习最长上升子序列（LIS）的时候，他让我想起了分治，但是动态规划却解决了子问题重叠的大问题，也就是说同一个子问题不求第二遍。所以说动态规划的实质就是记忆化搜索。

        子数组最大和这个问题是很经典典型的一维DP问题。用一层循环就可以搞定，最普通的DP算法复杂度是O(n)，比较理想。

        先描述一下这个问题。给第一个数组，如：2, -3, 2, 4, -1, 5。他的子数组最大和就是2 + 4 + (-1) + 5 = 10，我们可以看出，这里说的子数组不同于LIS/LCS中的子序列，这的子数组是连续的。

        最容易想到的算法，肯定是搜索，从所有可能性当中找出和最大的一种。这种算法的复杂度是指数级的O(2n)，是惨绝人寰的。

        所以我们来瞧瞧动态规划的解法。假定数组为a（下标0到n-1），d[i]则表示以a[i]为末尾的最大子数组和。所以上述序列中：

        从上面可以得知，状态转移方程为：d[i] = max(d[i-1] + a[i], a[i])，成立条件为i > 0，因为i = 0是，d[i-1]显然不对。

        对于这个方程的理解，可以这样想：数组全是整数的时候，显而易见，子数组最大和就成了这个数组求和的问题，如果还用DP来写，d[i]就存储着a[0] – a[i]的和，递推起来就是d[i-1] + a[i]（a[i]前面所有数字之和加上a[i]）。如果数组含有负数，a[i]就可能比前面的最大和要大了。所以状态转移方程是：max(d[i-1] + a[i], a[i])这么写的。

        我看到很多同志喜欢把动态转移方程中的max()用if()语句来代替，虽然效果一样，不过我觉得用max这样直白的表达式可读性更强。有不少同志喜欢定义一个int max(int a, int b)函数来返回a，b中的最大值，不过用宏来定义效率更高，所以我是用define来写的。另外ans = max(d[i], ans)这一句不属于动态转移方程，只是用来更新ans变量记录的最大值的，如果d[i] > ans，ans就应该更新为d[i]。

        求子数组最大和函数中的for()语句，初始时i = 1，这就是因为上面说的，i = 0时，d[i-1]会导致错误。有的版本会在for()循环体中加入判断：if(i > 0)，不过这样，就会产生很多次没必要的判断，效率就会变低。

        所以干脆从循环之前初始化d[0]，让他和ans都等于a[0]。然后循环从i = 1开始。这种初始化的方法在DP当中也是很常见的。