Problem description:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution:

For this question, we can use an algorithm called Kadane’s Algorithm. By maintaining two variables, max_endhere and max_sofar, we can calculate the maximum continuous subarray sum.

For example:
[2,-3,4,5]
i= 0: max_endhere= 2,max_sofar= 2
i= 1: max_endhere= -1,max_sofar= 2
i= 2: max_endhere= 4,max_sofar= 4
i= 3: max_endhere= 9,max_sofar= 9

[-2,-3,-1]
i= 0: max_endhere= -2,max_sofar= -2
i= 1: max_endhere= -3,max_sofar= -2
i= 2: max_endhere= -1,max_sofar= -1

1
2
3
4
5
6
7
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur, res = nums[0], nums[0]
        for num in nums[1:]:
            cur = max(num, cur+num)
            res = max(res, cur)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_endhere= 0, max_sofar= INT_MIN;
        
        for(int i= 0; i< nums.size(); i++){
            if(max_endhere<0)
                max_endhere = nums[i];
            else
                max_endhere+= nums[i];
            
            max_sofar= max(max_endhere, max_sofar);
        }
        return max_sofar;
    }
};

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://www.geeksforgeeks.org/?p=576/