53 最大子数组和

解题思路：
\qquad 1）前缀和
\qquad 上一篇刚写了用前缀和，解560 和为K的子数组这道题，没想到这么快就能用上，这里只不过把找和为K的子数组变成了和最大的子数组。 在一次遍历中，使用变量pre记录以位置i为结尾的前缀和pre = pre + nums[i]。同时记录一个前缀和的最小值mini，则以i为结尾的子数组和最大为pre - mini。在遍历过程中不断记录子数组和的最大值输出即可。

	int maxSubArray(vector<int>& nums) {int ans = nums[0], pre = 0, mini = 0;for(auto n : nums){pre += n;ans = max(ans, pre - mini);mini = min(mini, pre);}return ans;}

\qquad 2）动态规划
\qquad 前缀和和dp两种方法写出的代码看起来差不多，但二者的思想还是差很多的。
\qquad 对于当前元素n，dp看重的是n是否在目标子数组中。那么就有两种可能，n在目标子数组中，此时和为f(n-1) + n；或者n不在子数组中，从n开始构建新的子数组，此时和为n。由于题目要求最大子数组和，所以需要在两种情况之间取较大的那种，可以得到dp的递推公式：
\qquad \qquad \qquad \qquad \qquad \qquad f(n) = max(f(n-1) + n, n)
遍历所有的n，在过程中同时记录最大值即可。

	int maxSubArray(vector<int>& nums) {int ans = nums[0], pre = 0;for(auto n : nums){pre = max(pre + n, n);ans = max(ans, pre);}return ans;}

\qquad 观察两种方法，前缀和是从子数组的维度取考虑问题的，更直观一些；
\qquad dp则是站在数组每一个元素的角度，找到当前元素与上一元素之间的关系，逐步递推，从局部最优推出全局最优，有点类似数学归纳法。