Maximum Subarray

Medium

Python

def max_subarray(nums):
    cur=best=nums[0]
    for n in nums[1:]:
        cur=max(n,cur+n)
        best=max(best,cur)
    return best

Java

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

Key Insight

Kadane's. max() vs Math.max().

Python → Java Differences

max() vs Math.max()
nums[1:] slice vs index
Kadane's identical

Python

def max_subarray(nums):
    cur=best=nums[0]
    for n in nums[1:]:
        cur=max(n,cur+n)
        best=max(best,cur)
    return best

Java

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

Algorithm Steps

1. Track current and best
2. Restart or extend

← Previous All Arrays Next →