Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python

0:00 - Cubic solution
2:02 - Quadratic solution
3:10 - Linear solution
6:37 - Coding

#Coding #Programming #CodingInterview

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[peteaustin]

Hey man, i'm a postgrad CS student who didn't do anywhere near enough programming during my spare time in my bachelors. Your algorithms are really helping me think differently, thank you.

[karanssh]

Excellent explanation. For anyone curious, the algorithm in question in the O(N) solution is kadane's algorithm

[SidharthSharma]

Thanks for the series. Also Solution for the case where all numbers in array are negatives is returning the max number (which will be least negative number)
int max = nums[0];
int curMax = 0;
int maxNumber = INT_MIN;
for(int i=0;i < nums.size();i++)
{
curMax = curMax + nums.at(i);
if( curMax < 0)
{
maxNumber = std::max(maxNumber, curMax);
curMax = 0;
}
else
max = std::max(curMax, max);
}
return (max < 0) ? maxNumber : max;

[fikrewold]

Just did an interview with Amazon! This was the question.
Unfortunately, I was thinking differently! Wish, I had watched this very well.

[licokr]

I've searched Kadane's Algorithm and solved this problem after understanding first. But I don't know how to explain this, so I've watched your video. I knew this I would learn from your video even after solving a problem without much problems. I learn from your videos how to think about a problem more than how to solve a problem. Negative values don't contribute anything to get the maximum number, that is why it intializes to zero to throw the previous max number which is a negative number. Great, thanks a lot!👍

[DanielAkproh]

But if all negative results are disregarded, doesn't that exclude the case where all integers of the given array are negative?

[SumTsuiTechie]

I think the part for whether to keep the prefix is: if (n > n + curSum) curSum = n; else curSum = curSum + n.

In human language means if me alone is better than all of us combine, you guys are no use for me.

[randomBoulevards]

Even more concise and easy to understand solution possible:

# initialise both variables to negative infinity:

maxSub, curSum = float('-inf'), float('-inf')
for n in nums:
curSum = max(curSum + n, n)
maxSub = max(maxSub, curSum)
return maxSub

[Dhruvbala]

I find it easier to understand Kadane's algorithm as bottom up DP optimized for constant memory. The max subarray sum starting at index i is nums[i]+max(0, dp[i+1]). In other words, it's the maximum of choosing to keep just nums[i] or include the maximum of elements after it (which may be negative)

[galinalazareva]

Do you have any ideas about the Leetcode follow-up question for that problem? "Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle." Seems, they've added the follow-up recently

[bibeksharma]

Another Sliding window appraoch with two pointers:
Python Soln:

maxS = nums[0]
summ = 0

i, j = 0, 0

while j<len(nums):

if summ<0:
summ = 0
i=j
else:
summ = summ + nums[j]
maxS = max(maxS, summ)
j+=1

return maxS

[toolworks]

I think leetcode added new test cases since this solution was uploaded. My initial attempt was like this but the input array [-1] broke it. My solution when "resetting" the subTotal to zero was to instead check to see whether the new subTotal is less than the value itself (previous sum + currentVal < currentVal). I initialised the max_sum as negative infinity to allow for the fact that subarrays can have sums less than zero, but it did feel a bit hacky using float() to do that.

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf')
current_sum = 0
for num in nums:
current_sum += num
if num > current_sum:
current_sum = num
if current_sum > max_sum:
max_sum = current_sum
return max_sum

[aaronw]

Love the way you explain things super easy to follow along

[giorgizazadze]

I would change to this because the code will fail if curSum is positive and the next element of the list is greater than curSum for example [1, 2]. (It also works for all negative numbers)

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxSub = nums[0]
curSum = 0

for n in nums:
if curSum + n < n:
curSum = 0
curSum += n
maxSub = max(curSum, maxSub)
return maxSub

[tlee-tb]

Here's my additional thoughts on the third solution, Kadane's algo. It works by basically directly locating the start of the subarray while updating the end of the subarray (which is what the single loop is doing).

Compared to the quadratic solution, Kadane's algo skips the outer loop, because whenever the curSum < 0, resetting it to 0 is the same effort of chopping off the front portion/placing the start of the subarray to the correct stating index, aka. getting rid of all combinations with a starting index being anyone in the front portion. And if this starting index proceeds to the end within this current round in the loop without curSum ever becoming negative, it automatically already got rid of the rest of the combinations with a starting index after this current starting index, since all those combinations afterwards can only lead to a smaller sum because they will be a shorter subarray missing this positive front portion to be added that could make it bigger. That's why Kadane's algo can be linear because it basically gets rid of the outer loop in the quadratic solution.

[gplambi]

Great explanation but i have one doubt .. There may be an array of all negative numbers and in such scenario, one subarray may sums up to -5 other subarray to -10 so -5 will be the answer. So curSum < 0 may not work in this case. Please correct me if i am wrong.

[Andrew_J]

A solution that works the same but is a bit less clear is

def MaxSubArray(nums):
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1]
return max(nums)

[elizabethr]

One of the best and cleanest solutions, I have ever seen.

[sahilverma]

A little simple approach
a=[-2, 1, -3, 4, -1, 2, 1, -5, 4]
v=0
for i in range(len(a)):
for p in range(len(a[i:])):
if v<sum(a[i:][:p+1]):
v=sum(a[i:][:p+1])
print(v)

[sachinshaji]

For the code to work in any scenario(All Negative, All Positive, Mix) make this change:
for n in nums:
if curSum< 0:
curSum= n