Solution to Leetcode’s Maximum Subarray

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

ALGORITHM

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.

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;
}

OUTCOME

IMPROVEMENT
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:

IMPROVED CODE

 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;
    }

LESSONS
1.Don’t always be 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. Please leave a comment.