Maximum Subarray

Given an array of integers, find a contiguous subarray which has the largest sum.

求数组中间的一段, 就长减短

PrefixSum[i] = A[0] + A[1] + … A[i – 1], PrefixSum[0] = 0

易知构造 PrefixSum 耗费 O(n) 时间和 O(n) 空间

如需计算子数组从下标i到下标j之间的所有数之和

则有 Sum(i~j) = PrefixSum[j + 1] – PrefixSum[i]

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> &nums) {
        // write your code here
        int size = nums.size();
        if (size == 0) {
            return 0;
        }
        int minMax = 0;
        int maxSum = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum+= nums[i];
            maxSum = max(maxSum, sum - minMax);
            minMax = min(minMax, sum);
        }
        return maxSum;
    }
};