Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Solve it yourself: neetcode.io/problems/maximum-...
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. - Věda a technologie
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
great explanation
Thanks
I love neetcode
Excellent explanation. For anyone curious, the algorithm in question in the O(N) solution is kadane's algorithm
Kadane!!!! If I get into FAANG, I will leave a rose to your tombstone Kadane!
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.
Its never too late
@@thiswasme5452 If you were curious as to how this helped me, I am now working as a software engineer for a good organisation and I also aced my postgrad academic studies :)
@@peteaustin5018 Ohh great!! Nice to hear that 😊.
@@peteaustin5018 Yeee that's awesome, dude!
@@peteaustin5018 that's great.
But if all negative results are disregarded, doesn't that exclude the case where all integers of the given array are negative?
If all elements are negative integers, the max subarray will just be the maximum integer, because adding any negative value to an integer will make it smaller. And we will get this max integer, because we will reset the subarray every iteration and check for the max value.
@@TeamDUSTOfficial Well but the current sum was set for zero, and it'll be the result after the max function so the maxSub will be zero instead of the first element
@@somewheresomeone3959 You're adding the value of n at every iteration in the line `curSum += n` before the comparison so curSum won't be zero
@@TeamDUSTOfficial tanx man I got it here
Exactly what I was thinking!
great stuff brother, your explanations are so good by themselves, I dont even have to watch you code it up it just makes sense
Love the way you explain things super easy to follow along
Of all the explanations on this algorithm, this video is the best. Thanks Man
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)
Just did an interview with Amazon! This was the question.
Unfortunately, I was thinking differently! Wish, I had watched this very well.
You ethiopian I reckon from your profile. Did you land a job at faang?
what role?
These video solutions are changing my life. Thanks Neet!
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.
This case will only happen if the curSum is negative anyways
@@sahil_tayade that particular part I didn't understand in that solution... what if the previous curSum was even less than that and less than zero too...
I agree with this, in the case explained by @NeetCode, if the array is filled with only negative values, then the max would be 0, even if 0 doesn't exist in the array.... So, the check provided by @SumTsuiTechie sounds like a good approach to resolving that.
n > n + curSum => n - n > n - n + curSum => 0 > curSum => curSum < 0
One of the best and cleanest solutions, I have ever seen.
I forgot to thank you again for a great explanation. You are my savior!
Thank you so much for your videos! They've been exceptionally helpful.
Great video and explanation! Could you also explain how to solve the max subarray problem with divide and conquer? Thanks in advice!
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!👍
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;
Thanks, great explanation and good visuals.
This is such a simple and effective explanation. Thanks a lot, man :)
Thank you Sir. I have made a silly mistake in this problem now it's clear.
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
love ur tone and voice so much, good for listening the content into my brain
Thanks for the video, it was super helpful
Hi, what device and software do you use for draw the figures by free hand and use it in your screen recording?
I hear his mouse clicking, so likely just mouse. And there are many sw for over-the-screen drawing, like gInk.
Thanks for the video. Very happy to find this video
this teaches us the real working of kaden's algo....awesome question!
I think you have to first add the total, and then check the condition if total is zero.
amazing,
could you please make this q with divide and conquer?
breaking up the video into different operation times >>>>>
In my opinion, this is de best video that I have found about this problem
Does this solution work if the array contains only negative integers?
beautiful explanation as always. Thank you
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
czcams.com/video/yBCzO0FpsVc/video.html divide n conquer, this might help
ChatGPT gave this solution for divide and conquer:
def maxSubArray(nums):
def divide_and_conquer(nums, left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
# Find the maximum sum subarray in the left half
left_max = float('-inf')
curr_sum = 0
for i in range(mid, left - 1, -1):
curr_sum += nums[i]
left_max = max(left_max, curr_sum)
# Find the maximum sum subarray in the right half
right_max = float('-inf')
curr_sum = 0
for i in range(mid + 1, right + 1):
curr_sum += nums[i]
right_max = max(right_max, curr_sum)
# Find the maximum sum subarray crossing the middle element
cross_max = left_max + right_max
# Recursively find the maximum subarray sum in the left and right halves
return max(cross_max, divide_and_conquer(nums, left, mid), divide_and_conquer(nums, mid + 1, right))
# Call the divide and conquer function to find the maximum subarray sum
return divide_and_conquer(nums, 0, len(nums) - 1)
explanation: The idea behind this algorithm is to divide the input array into two halves, and recursively find the maximum subarray sum in the left and right halves. The maximum subarray sum can either lie entirely in the left half, entirely in the right half, or cross the middle element. The maximum subarray sum that crosses the middle element can be found by computing the maximum sum subarray in the left half that ends at the middle element, and the maximum sum subarray in the right half that starts from the middle element.
The time complexity of this algorithm is O(n log n), where n is the size of the input array.
Did you get the solution for the follow up?
I'm also interested as to what this means
@@shriharikulkarni3986check the solution section in the leecode there is this one guy who showed 7 different solutions
what is the maximum sum is a negative number, the code would only output 0 then
Not really. Assume the array only contains negative numbers. At start maxSub will equal to first element. Then in every iteration we do reset maxSub to zero, but we immediately sum it with next number (a negative too) making it equal to that number. So it will check first element against each next element, each time updating maxSub to the max of two. That's just classic "find max" one-pass algorithm.
In addition to what Сергей said, notice how we are storing the max element in maxSub and then returning that. So in the case of an array containing all negative numbers, it will return the maximum negative number.
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
Does it guarantees that it has positive numbers too? I saw this solution in the solutions of leetcode and I was confused as why it works.
what if the edge case of all negative numbers, is empty sub-array allowed ?
what if i need to print the index values:
will it take another loop and it make another o(N)
or any other approach rather than loop?
could anyone help me????
Thanks in advance
Why does the runtime is so big when submitting to leetcode? Is this time related to a bunch of robustness tests right?
Beautifully explained!
Thanks for the video bro!
What about if the test case was an array of all negative integers? Wouldn't we end up returning zero when the actual answer is the least negative of those given integers? Since curSum is initialized to 0 and at no point will our "max(maxSub, curSum)" code return anything other than 0 since it will always be higher than a negative number ?
very good explanation, Thanks
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)
Hi sir. What if the array is [-1,-2,-3,-4] like this?
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
I guess you can add an if statement if the max number in the array is negative, just output the max number
if max(nums)
it will work irrespective of input
max=-1
sum=0
-----
for loop
-----
sum=-1
max =-1
------
sumsum
so max will remain -1
----
and so on
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
m = nums[0]
s = nums[0]
for n in nums[1:]:
if n > s and s < 0:
s = n
else:
s += n
m = max(m, s)
return m
It still works
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.
Thank you, I really understood it. but did we use dynamic programming in this solution?
This way of solving this problem is known as Kadane's Algorithm.
Kadane’s Algorithm is an *iterative dynamic programming* algorithm in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.
i tried to code in c++ but failed :( what should be the approach/code for in c++
but where is the condition to remove the negative values
Wow. This is actually genius.
This was the easiest explanation and solution of this problem. Played it at 1.5x and was able to understand
what happens if all the values are negative in the array ?
the curSum will always reset to each negative number in the array and the maxSub will keep the highest number
add this at the end of the forloop for a clearer understanding
print(f"curSum = {curSum} MaxSub = {maxSub}")
neetcode please return making videos with this keyboard.. I really get relaxed from this. Even if I solved this, I see the typing part! :>
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.
Great Explanation :)
One edge case is missing. What if all numbers are negative [-1, -3, -4]. We need to return -1. But this algorithm will return 0.
It won't, the code keeps track of the max sum seen. Inside the loop, it initializes the current sum to 0 if it's negative, then proceeds to add the current number (negative in this case) to the current sum. Then, if the current sum is bigger than the max sum seen, it will set max sum to the current sum (in this case a negative). It will keep track of the smallest negative seen (the smaller a negative the bigger it is compared to other negatives).
Hi! Thank you for the video, it provided me with a few insights. One question, so this algorithm won't work if the array contains only negative numbers?
It doesn't matter, since when you come to nums[p] if the preSum < 0, you set it back to 0, and now current sum is just nums[p], then you use max() to recored the new maxSum, even if all numbers is negative, if nums[p] is the biggest one, you will find and record it in this step
Doesn't resetting curSum to 0 assume that there are values in our array that are >= 0? What if all our values are negative?
i though there is no intuition behind this algo, i just need to memorize it, but you changed my mind
but if we put curSum
thanks man, big help!
If I want to return both subarray and the maximum sum how can i do that
Can't you just set the curSum to the current number if maxSub < curSum?
This was very helpful, please make a Divide and conquer solution for this too.
Can you make a video for 163. Missing Ranges.. Your videos have been succinct and very helpful.
I dont understand why if current sum is negative then it doesnt contribute anything can you explain more on this issue?
Does sorting work on this problem? And Keep adding the numbers till the value decreases?
This solution wouldn't work for the case where all numbers in the array are negative, would it?
Smart solution! (This should be a medium question.)
What if the whole array is made of negative numbers? Would this still work?
Hey, quick question about the linear time solution, would this code blow up given an array of all negative values?
still work, the max element value of the array will be the answer
@@qqqqoeewqwer I don't think that it will work
as my input is [-1]
or [-2,-2,-3,-1,-4,-5]
because by this code answer will 0
@@dontdemotivate6575 have you tried running the code yet? Answer is not going to be zero, since there is the maxSum variable that stores the answer to your example: [-2,-2,-3,-1,-4,-5].
it won't. best way to learn this is to run this code and print the part that you are unclear. given all negative number the max() function will return the largest negative number of the array
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
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
the optimized solution works for this, since we're always initializing the max sum to the first number in the array and adding the current number to the currentSum before deciding whether it should replace the previous max. So, an array of [-1] would start with max of -1 and current of 0, then hit the loop. In the loop it would first add 0 + (-1) and then compare -1 (curSum) to -1 (maxSum).
IMO the minimum sum should always be 0 since an empty subarray should add to 0, but hey, i guess the problem calls for a subarray of at least one item.
just add
if(maxSum
Initially, I confidently declared, "I don't even need a pen and paper to solve it in O(n) time." But as I struggled, scratching my head in confusion, I eventually found myself here, seeking assistance and realizing that maybe a pen and paper wouldn't have been such a bad idea after all.
hey what if the whole array is negative.. will it work??
hey i have a doubt, when I have coded in python the line i have added was
if cursum
This will fail when there's an array containing only negative numbers.
In this scenario, the result should be the max number in the array, but your solution will return 0
Thanks for the explanation :D What if we wanted to create a subarray of the maximum? so in your example it would output [4, -1, 2, 1]
Lovely solution but as others have pointed out, this fails the leetcode 53 test suite because that has things like [-2, -1] as test patterns whereas by resetting to 0 constantly it won't work for those.
If all the elements are negative then how we get max subArray
Hi, i was just thinking about it, but if all numbers are negative, wont your answer be returning 0, which is not inside the array?
No, it will return the biggest numbers in the array.
@@mowww20 Then why are we setting currentsum to 0 if it's less than 0?
@owenwu7995 Setting currentSum to 0 is to reset where the sub array starts. maxSub is always going to return the bigger of the two sub arrays (current biggest total vs newest total)
why brute force is n^3 ?. It looks with n^2 , we can solve it. Can you explain why ?
You want your problems solved with the lowest time complexity and in the video, he achieved n^1
I think starting current with 0 is wrong. Apparently this is not in the test cases but the array could be [-3, -2, -1] so max sub array would be -1. I say we should compare the current subarray with the current number instead of 0, like so;
def maxSubArray(self, nums: List[int]) -> int:
maximum = current = nums[0]
for i in range(1, len(nums)):
current = max(current+nums[i], nums[i])
maximum = max(maximum, current)
return maximum
I agree
the answer would still be -1 because after current is set to 0, it still performs += num which for e.g is -1, hence when perform max(max, current), -1 would still be the result
I don't not fully understand the if (cursum < 0) part. why 0?
you'll get a lower answer than the highest max you can get if you don't reset it to 0, and you can't set it higher than zero because your total will be higher than the max sub array. you can get away with "forcing" a current sum of zero because it helps you reach your maximum.
DP solution FYI:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[len(nums) - 1] = nums[len(nums) - 1]
for i in range(len(nums) - 2, -1, -1):
dp[i] = max(nums[i], nums[i] + dp[i + 1])
return max(dp)
What if the maximum is a negative number ?
What happens that the all the array is negative?
Another Sliding window appraoch with two pointers:
Python Soln:
maxS = nums[0]
summ = 0
i,j = 0,0
while j
Thanks! this is much easier to understand!
wait, we don't need the i pointer.
will this work if all the elements are negative?
why are negative values ignored? what if all the elements are negatives?
that case you have to find minimum negative number right? somebody answer this.
You're right, if all the elements are negative the answer will be the greatest negative. Lines 7 and 8 clear the curSum everytime so that we don't add up more than one negative number, and then we 'reinitialize' curSum with the current value, and check if it's bigger than the one we have.
I agree that this is a pretty neat way to do it. If I had come up with the solution by myself I would never had thought of something so elegant
The question says to try 'divide and conquer'?
high quality content
Why are you making curSum =0, because max sum can be negative also right?
Could you please make a video for the leetcode 1335?
They've asked for the divide and conquer approach, can u give that solution ?
for n in nums:
if curSum < 0:
curSum = 0
curSum += n
maxSum = max(maxSum, curSum)
curSum = maxSum
return maxSum
I think this logic is better as it will handle all negative values as well
What if they are all negative numbers. I do not think the solution would handle that.
Perhaps explain why all negative input array will work too.
Because the maxSub holds the current max and if you keep adding negatives together its turns to a bigger negative so you would return the highest negative number in the array
is it possible the max sum is negative?
Thanks a lot sir :)
I don't think we should remove the negative as we might have an array of negative numbers
I thought the same and struggled with it that's why I came here. Reality is that from an array of negative numbers you should pick the largest of those numbers as your largest sum. The solution sets the current sum to zero if it's negative but then adds the current number (which is negative) to the current sum (which is zero) and compares it to the largest sum. So the largest number out of those negative numbers gets selected eventually.
Updated code from the NeetCode website shown below. (The code in the video may not have the right order in terms of resetting the total vs updating the result)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
total = 0
for n in nums:
total += n
res = max(res, total)
if total < 0:
total = 0
return res
Thanks
Makes it look more intuitive
why do we check if total is < 0 ?
what if all the array elements are negative? won't maxSub return 0?
no, it will just go through each the elements in curSum and keep the biggest in bestSum