Blog

Here’s the question link on LeetCode 53. Maximum Subarray:

https://leetcode.com/problems/maximum-subarray/description

Brute O(n^2)

Try all possible subarrays using nested loops; whichever is the max is the solution.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // brute force:
        // try each subarray
        int maxR = INT_MIN;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            int currSum = 0;
            for(int j = i; j < n; j++) {
                currSum += nums[j];
                maxR = max(maxR, currSum);
            }
        }
        return maxR;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // brute force:
        // try each subarray
        int maxR = INT_MIN;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            int currSum = 0;
            for(int j = i; j < n; j++) {
                currSum += nums[j];
                maxR = max(maxR, currSum);
            }
        }
        return maxR;
    }
};

As the constraints are huge, this hits TLE:

Optimal – O(n)

As the values can go negative, we cannot use a sliding window here.

Why can we not use prefix sums?

Let’s first understand why the obvious approaches don’t work.

We absolutely can use prefix sums to solve this problem.

Remember, the sum of a subarray from index i to j is:

prefix[j] – prefix[i-1]

But here’s the catch.

For every index j, we need to find the smallest prefix sum that occurred before it to maximize the difference.

If we simply calculate prefix sums and try every possible pair, we’re back to O(n²).

We could optimize this to O(n) by maintaining the minimum prefix sum seen so far. So prefix sum isn’t wrong; it’s just another way of arriving at an O(n) solution.

Why does Kadane’s work?

Let’s take an example:

nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Imagine we’re traversing the array and maintaining the sum of the current subarray.

Here’s the observation:

If our current subarray sum becomes negative, carrying it forward is pointless.

Why?

Suppose we have a current sum of -2, and the next element is 4.

Our new sum would be:

-2 + 4 = 2

But starting a new subarray from 4 gives us 4, which is obviously better!

A negative sum only decreases the sum of any subarray we extend it with.

So whenever our current sum becomes negative, we discard it and start fresh from the next element.

That’s the entire intuition behind Kadane’s Algorithm.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //using kadane's algorithm
        int maxR = nums[0];
        int currSum = 0;
        for(int num : nums) {
            currSum += num;
            maxR = max(maxR, currSum);

            if(currSum < 0) {
                currSum = 0;
            }
        }
        return maxR;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //using kadane's algorithm
        int maxR = nums[0];
        int currSum = 0;
        for(int num : nums) {
            currSum += num;
            maxR = max(maxR, currSum);

            if(currSum < 0) {
                currSum = 0;
            }
        }
        return maxR;
    }
};

That’s it see you in the next one.