算法思路（动态规划）

• 设dp[n]为以第n个数为结尾，得到的子数组的和的最大值，因为以第n个数为结尾所以array[n]是必然被选择的。
• 基于dp[n-1]的值，如果dp[n-1]>0，我们加上这个正数，我们的值是不是必然会增大；如果dp[n-1]<0,那么我们加上负数，我们的值就会减小，这个时候我们不如不要前面的结果，只要当前这个数，结果反而更优。
• 于是我们就得到了状态转移方程dp[n]=array[n]+(dp[n-1]>0?dp[n-1]:0)，实时跟ans比较，更新最大值即可。

代码实现

当然对这一道题来说，我们不用定义一个dp数组，而只定义一个now变量来代替dp数组，如果now<0，那么就令now=array[i]。如果now>0，那么就令now+=array[i]。

//典型的动态规划题
class Solution
{
public:
  int FindGreatestSumOfSubArray(vector<int> array)
  {		
  		//now代表各个状态，ans保留最大的那个状态。
	    int now, ans;
	    now = 0, ans = INT_MIN;
	    for (int i = 0; i < array.size(); i++)
	    {
	        if (now < 0)//now<0,则舍去前面的
	            now = array[i];
	        else
	        {
	            now += array[i];//比0大则直接加上去
	        }
	        ans = max(now, ans);//更新ans
	    }
	    return ans;
  }
};