题目描述：一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

方法1：求得该数组的前缀和数组，题目就变成了买卖股票的最佳时机（前缀和数组类比为股票价格）

不断遍历数组计算前缀和。当前的前缀和（卖出价格）减去之前的前缀和的最小值（买入价格），就得到了以当前元素结尾的子数组和的最大值（利润），用它来更新答案的最大值（最大利润）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre_sum = 0;
        int min_presum = 0;
        int m = nums[0];
        for(int i=0;i<nums.size();i++){
            pre_sum += nums[i];
            m = max(pre_sum - min_presum,m);
            min_presum = min(min_presum,pre_sum);
        }
        return m;
    }
};

方法2：动态规划，d(i)表示以nums[i]结尾的最大子数组和，所以

d(i) = max(d(i-1)+ nums[i],nums[i])

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int m = nums[0];//保存最大子数组和
        int dp = nums[0];
        for(int i=1;i<nums.size();i++){
            dp = max(dp+nums[i],nums[i]);
            m = max(m,dp);
        }
        return m;
    }
};

方法3：贪心，只保留大于0的之前和，保证当前和不会小于当前值

四个变量，当前值，之前和，当前和， 当前最大子数组和

当前和(i) = (当前值(i) + 之前和(i-1))

之前和(i) = max(0,当前和(i))

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int m = nums[0];
        int nowsum = nums[0];
        int presum = max(0,nums[0]);
        for(int i=1;i<nums.size();i++){
            nowsum = nums[i] + presum;
            m = max(m,nowsum);
            presum = max(0,nowsum);
        }
        return m;
    }
};