Solution to Leetcode’s Maximum Subarray

This is an easy Leetcode problem 53. See below image for description:

Leetcode 53: problem description

FIRST APPROACH

I knew the brute force solution to this problem when i saw it, but then doing the brute force solution would be brutally slow.

I had read an article and watched a YouTube tutorial on sliding window algorithm for some problem I was solving earlier. For some reason, Sliding window algorithm came to my mind 🤣🤣🤣. So i jumped into trying to solve problem using sliding window unfortunately that didn't work out 😩😩 (I still believe its possible to solve it with sliding window..).

After a moment of torture and frustration(😩😩) trying to solve with this algorithm, had to work with a version of Kadane’s algorithm of maximum product of subarray. The algorithm is as follows:

1. Have a global variable currentSum;
2. Have a global variable max that will also be the return value;
3. loop through the array, check if the current element (nums[i]) is greater than the current sum and current element put together (i.e currentSum + nums[i]);
4. if it is greater, reassign the currentSum variable to be the current element, nums[i];
5. if it is not, reassign the currentSum variable to be the summation of both the existing current sum and the current array element (currentSum = currentSum + nums[i])
6. finally, check if the currentSum is greater than the current maximum. if it is, reassign the current max to be equal to currentSum.
7. Then return max.

The above may seem confusing, but trust me, its as simple as ABC. The runtime for this algorithm is O(n) where n is the length of the array.

CODE

public static int maxSubArray(int[] nums) {

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

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > (currentSum + nums[i]))
            currentSum = nums[i];
        else
            currentSum = currentSum + nums[i];

        if (currentSum > max) {
            max = currentSum;
        }
    }
    return max;
}

OPTIMIZATION

There is no much optimization to be done to this algorithm unless to try to solve it in O(log n). All we can do is just to make the code a bit cleaner by using the library function, Math.max().

Math.max checks the maximum/bigger value between two numbers. So we can replace those if statements with Math.max(). Cleaner code is shown below:

public static int maxSubArray(int[] nums) {

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

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

        //cleaner and simple
        currentSum = Math.max(nums[i], currentSum + nums[i]);

        max = Math.max(currentSum, max);
    }
    return max;
}

OUTCOME

LESSONS

1. Don’t always been in the box of a particular algorithm you thought would work, just the way i thought Sliding window would work.
2. Using library functions where and when needed.

Thank you for reading and please leave a comment.