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

Notice

The subarray should contain at least one number.

Have you met this question in a real interview?

Yes

Example

Given the array[−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray[4,−1,2,1]has the largest sum =6.

Challenge

Can you do it in time complexity O(n)?

optimize space complexity to O(1)

initial value of maxSum, sum, minSum is important

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.empty\(\)\) {

        return 0;

    }

    int local = nums\[0\], global = nums\[0\];

    for \(int i = 1; i < nums.size\(\); ++i\) {

        local = max\(local + nums\[i\], nums\[i\]\);

        global = max\(global, local\);

    }

    return global;

}

};