Maximum Subarray — Kadane's Algorithm

Problem

Find the subarray with maximum sum. At least one element.

Example: [-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1])

Approach — Kadane's Algorithm

curr = max(nums[i], curr + nums[i]). Track global max.

Time: O(n) | Space: O(1)

Solutions

C

int maxSubArray(int* nums, int n) {
    int curr=nums[0],best=nums[0];
    for(int i=1;i<n;i++){
        curr=nums[i]>curr+nums[i]?nums[i]:curr+nums[i];
        if(curr>best)best=curr;
    }
    return best;
}

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums){
        int curr=nums[0],best=nums[0];
        for(int i=1;i<nums.size();i++){curr=max(nums[i],curr+nums[i]);best=max(best,curr);}
        return best;
    }
};

Java

class Solution {
    public int maxSubArray(int[] nums){
        int curr=nums[0],best=nums[0];
        for(int i=1;i<nums.length;i++){curr=Math.max(nums[i],curr+nums[i]);best=Math.max(best,curr);}
        return best;
    }
}

JavaScript

var maxSubArray = function(nums) {
    let [curr,best]=[nums[0],nums[0]];
    for(let i=1;i<nums.length;i++){curr=Math.max(nums[i],curr+nums[i]);best=Math.max(best,curr);}
    return best;
};

Python

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        curr=best=nums[0]
        for n in nums[1:]:
            curr=max(n,curr+n); best=max(best,curr)
        return best

Complexity

Time: O(n) | Space: O(1)

Key Takeaway

Kadane: either extend or restart. curr = max(x, prev + x).