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.

思路一：暴力搜索，最笨的方法

代碼如下：

class Solution {public:    int maxSubArray(vector<int>& nums) {        int size = nums.size();        int max = 0x80000000,sum=0;        for(int i=0;i<size;i++)        {            sum = 0;            for(int j=i;j<size;j++)            {                sum += nums[j];                if(sum > max)                    max = sum;            }        }        return max;    }};
已哭暈在廁所，想想怎么優(yōu)化
思路二：尋找特性，進行減枝操作。當sum小于0時，其加上后面的數(shù)只會使得sum更小，所以此時sum與max進行對比，然后就sum置為0，從下一個位置開始計算
代碼如下：
class Solution {public:    int maxSubArray(vector<int>& nums) {        int size = nums.size();        int max = 0x80000000,sum=0;        for(int i=0;i<size;i++)        {            sum += nums[i];            if(sum > max)                max = sum;            if(sum < 0)                sum = 0;        }        return max;    }};