Maximum Subarray

要记录以下三个值:

sum = 0;

maxsubarray_sum = INTMIN;

minsum = 0;

code

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
        if(nums.size() == 0)
        {
            return -1;
        }

        int sum = 0;
        int minsum = 0;
        int ret = numeric_limits<int>::min();

        for(int i = 0; i<nums.size(); i++)
        {
            sum += nums[i];
            ret = max(ret, sum-minsum);
            minsum = min(minsum, sum);
        }

        return ret;
    }
};

results matching ""

    No results matching ""