53. Maximum Subarray
题目描述：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
题目翻译
在一个数组中找出一个连续的子串使得它们的和最大。
例如，给出数组 [-2,1,-3,4,-1,2,1,-5,4]，它有一个和最大的子串为[4,-1,2,1]，和为6。
解题方案
标签： Dynamic Programming
思路：
- 这是一道非常经典的动态规划的题目
- 基本思路是这样的，在每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。
- 接下来说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第i+1步的表达式是：local[i+1]=max(A[i],local[i]+A[i])，就是局部最优是一定要包含当前元素，所以不然就是上一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]； global[i+1]=max(local[i+1],global[i])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()==0)
return 0;
int global = nums[0];
int local = nums[0];
for(int i=1;i<nums.size();i++)
{
local = max(nums[i],local+nums[i]);
global = max(local,global);
}
return global;
}
};