# Solution to Leetcode’s Maximum Subarray

This is an easy Leetcode problem 53. See below image for 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:

- Have a global variable
*currentSum**;* - Have a global variable
that will also be the return value;*max* - 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]); - if it is greater, reassign the
*currentSum*variable to be the current element,*nums[i]*; - 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]*) - finally, check if the
*currentSum*is greater than the current maximum. if it is, reassign the current*max*to be equal to*currentSum.* - 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**

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

Thank you for reading and please leave a comment.