17.8 You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.

 

LeetCode上的原题，请参见我之前的博客。

 

解法一：

int get_max_sum(vector
     
       nums) {    int res = INT_MIN, sum = INT_MIN;    for (auto a : nums) {        sum = max(sum + a, a);        res = max(res, sum);    }    return res;}
     

 

解法二：

int helper(vector
     
       nums, int left, int right) {    if (left >= right) return nums[left];    int mid = left + (right - left) / 2;    int lmax = helper(nums, left, mid - 1);    int rmax = helper(nums, mid + 1, right);    int mmax = nums[mid], t = nums[mid];    for (int i = mid - 1; i >= left; --i) {        t += nums[i];        mmax = max(mmax, t);    }    t = mmax;    for (int i = mid + 1; i <= right; ++i) {        t += nums[i];        mmax = max(mmax, t);    }    return max(mmax, max(lmax, rmax));}int get_max_sum(vector
      
        nums) {    return helper(nums, 0, nums.size() - 1);}