Leetcode 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.

本题要找subarray里面最大的子序列的sum。

求最大值： dp， heap , 打擂台
本题用dp, 基本解法：M[i] 表示0-i including i the max subarray sum.
由于本题中， dp的induction rule只看M[i-1]位置的元素，所以不需要用一个array存储，可以直接用两个变量： pre， cur 来进行dp。 
时间复杂度: O(n), 空间复杂度： O（1）

class Solution {
public:
//use dp to solve
    int maxSubArray(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 0;
        //int M[nums.size()];
        //base case
        int M = nums[0];
        int pre = M;
        int maxl = M;
        for (int i = 1; i < nums.size(); i++) {
            if (pre > 0){
                 M = pre + nums[i];
            }
            else M = nums[i];
            maxl = max(maxl, M);
            pre = M;
        }
        return maxl;
    }
};