How to Solve the Maximum Subarray Problem on LeetCode [53]

We have to return the maximum sum of elements from a subarray belonging to the given array.

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

Nested Loops was the only solution that I got after half an hour of thinking. So i will write it down here, then I will try out the other proposed solutions, learning about their pros and cons.

Nested Loops

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int sum = nums[0];

        for (int i = 0; i < n; ++i) {
            for (int j = i, subSum = 0; j < n; ++j) {
                subSum += nums[j]; // a temp var that stores the sum of elements starting from
// element [i]
                sum = sum < subSum ? subSum : sum; // the sum var only stores the max sum that
// it encounters during the iteration from element [i].
            }
        }

        return sum;
    }
};

Time Complexity is O(n²).

Kadane’s Algorithm

This was an interesting take on the problem. It does not do anything too radical, but the the solution is beautiful.

This algorithm helps us find parts of a list where numbers add up to more than zero. Think of it this way: the very first number in a group should always matter. Even if some numbers after it are negative, the sum shouldn't become negative and make the whole group seem useless. The algorithm keeps going, hoping that more positive numbers will come along and make the total sum positive again.

My recommendation would be Youtube if you want to thoroughly understand what is going on.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int subSum = nums[0];
        int sum = 0;
        for (int i : nums) {
            sum += i;
            subSum = sum > subSum ? sum : subSum;
            sum = sum < 0 ? 0 : sum;
        }
        return subSum;
    }
};

Time Complexity is O(n).

Space Complexity is O(1).

So this is out answer, not.

Leetcode has asked us to try for a solution that implements divide and conquer method.

Divide and Conquer

I will admit, I still need more time to really understand what is going on. As someone who had a tough time with the same concept while learning merge sort, this was a bit too hard for me.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) {
            return 0; 
        }
        return maxSubArray(nums, 0, nums.size() - 1);
    }

    int maxSubArray(vector<int>& arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }

        int mid = L + (R - L) / 2;
        int leftMaxSum = maxSubArray(arr, L, mid);
        int rightMaxSum = maxSubArray(arr, mid + 1, R);

        int crossSum = 0;
        int currentLeftSum = 0;
        int leftSuffixMaxSum = INT_MIN;
        for (int i = mid; i >= L; --i) {
            currentLeftSum += arr[i];
            leftSuffixMaxSum = max(leftSuffixMaxSum, currentLeftSum);
        }

        int currentRightSum = 0;
        int rightPrefixMaxSum = INT_MIN;
        for (int i = mid + 1; i <= R; ++i) {
            currentRightSum += arr[i];
            rightPrefixMaxSum = max(rightPrefixMaxSum, currentRightSum);
        }
        crossSum = leftSuffixMaxSum + rightPrefixMaxSum;

        return max({leftMaxSum, rightMaxSum, crossSum});
    }
};

Yep, leetcode forced me to use max() funtion. :(

Time Complexity is O(nlog(n)).

Space Complexity is O(log(n)).

This is the solution that leetcode wanted us to try.

---

Anyways, have a good Day.