Maximum Subarray

题目：

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

接口：

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

    }
};

分析：

这道题目是典型的subarray prefix sum问题，假设前j个元素的和是sum[j]，前i个元素的和是sum[i]，那么从j + 1到i的subarray sum就是sum[i] - sum[j]。

在解题的时候，维护一个minSum, 然后每次计算完sum[i]的时候，sum[i] - minSum就有可能是max subarray sum。

最后强调一点，这道题目强调顺序，应该先做maxSum，后做minSum，这也保证了当数组只有一个元素的时候，依然符合规律。

解法：

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 sum = 0;
        int maxSum = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            maxSum = max(maxSum, sum);
            sum = max(0, sum);
        }
        return maxSum;
    }
};