Maximum Subarray

#java #leetcode #computerscience #algorithms

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

My First Thought (Brute Force)

The most straightforward approach is to generate all possible subarrays, calculate their sums, and keep track of the maximum sum encountered.

Brute Force Code

class Solution {
    public int maxSubArray(int[] nums) {

        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {

            int sum = 0;

            for (int j = i; j < nums.length; j++) {

                sum += nums[j];
                maxSum = Math.max(maxSum, sum);
            }
        }

        return maxSum;
    }
}

Complexity Analysis

Time Complexity: O(N²)
Space Complexity: O(1)

While this works, we're repeatedly recalculating sums for overlapping subarrays.

The Key Observation

Suppose my running sum becomes negative.

Current Sum = -5
Next Element = 4

If I continue:

-5 + 4 = -1

If I start fresh:

Clearly:

4 > -1

A negative running sum only hurts future subarrays.

This leads to a powerful insight:

If the running sum becomes negative, discard it and start a new subarray.

Kadane's Algorithm

Kadane's Algorithm maintains a running sum while traversing the array.

For each element:

Add it to the running sum.
Update the maximum answer.
If the running sum becomes negative, reset it to 0.

Optimal Solution

class Solution {
    public int maxSubArray(int[] nums) {

        int currentSum = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int num : nums) {

            currentSum += num;

            maxSum = Math.max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxSum;
    }
}

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(1)

Quick Dry Run

Input:

[-2,1,-3,4,-1,2,1,-5,4]

Element	Running Sum	Max Sum
-2	-2	-2
Reset	0	-2
1	1	1
-3	-2	1
Reset	0	1
4	4	4
-1	3	4
2	5	5
1	6	6
-5	1	6
4	5	6

Answer:

Subarray:

[4, -1, 2, 1]

Takeaway

Kadane's Algorithm is one of those elegant solutions that turns an O(N²) brute-force approach into an O(N) optimal solution through a simple observation: