/****************************
   Name:  Maximum Subarray 最大连续数组和
   Date: 01/28/2016
   Author: Hualin Li
   Description: This is the Maximum Subarray in the C++. 第二题选择的是DP，也许还是天意吧...
   做题感想：该题目有两种经典解法。我个人喜欢DP的解法。之前想了半个小时为什么这个方法可以
   凑效。后来在草稿上一比划就明白了，如果有朋友和我一个一开始卡住的话，只要记住两个要点：
   （1）从左往右加数列元素时，只要sum不为负数，这个sum就是有效有用的。（2）一旦sum为负数，
   则用sum=0来从新计数。
   
*****************************/
class Solution {
public:
    int maxSubArray(vector<int>&nums) {
        int sum=0;
	int getMax=INT_MIN;//That is the min value int can have 
		
         for(int i=0;i<nums.size();i++)
	{
	sum=sum+nums[i];
	getMax=max(sum,getMax);
	//If sum <0,reselect i for next candidate
	if(sum<0)
	sum=0;
	}
	return getMax;
    }
};