🥐LeetCode #53

Maximum Subarray - LeetCodeLeetCode

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Understanding Kadane's Algorithm

What is the core idea?

Kadane realized that when examining each subarray, we have two choices - either including the current element expands our maximum prefix sum so far, or starting a new prefix from this element. This allows us to track just two values as we iterate through the array.

Pseudocode

The pseudocode is:

Track current/overall maximum prefix:

maxCurrent = first element  
maxOverall = first element

Iterate through each element:

for i = 1 to length(arr):

  maxCurrent = max(arr[i], maxCurrent + arr[i])

  maxOverall = max(maxCurrent, maxOverall)

Breaking it down:

• Track best prefix so far in maxCurrent

• Compare including/excluding current element

• Update maxOverall after each iteration

We can find the optimal subarray in one linear pass this way!

Track current/overall maximum prefix:

int maxSum = nums[0];
int currentSum = nums[0];

Iterate through each element:

for(int i=1; i<nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + arr[i]);
    maxSum = Math.max(currentSum, maxSum)
}

From the Math Class:

Solution:

You must understand Kadane's Algorithm to answer this, as you literally copy its format.

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

        for(int i=1; i<nums.length;i++){
            currentSum= Math.max(nums[i], currentSum+nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}