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)
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.
@@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.
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
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.
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
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.
@@geraldo_silva it won't, test this entire code. cursum = 0 maxsub=nums[0] for n in nums: if cursum < 0: cursum = n else: cursum += n maxsub=max(maxsub,cursum) print(maxsub)
I started doing LeetCode for the first time yesterday.... I have a six star in Problem Solving on Hackerrank and it just threw me over a cliff and smashed my organs on this Two Sum problem... My first problem on Leetcode was adding two numbers and then it jumped to this Two Sum
Could someone explain why the two-pointer approach, where one pointer starts at the beginning and the other at the end of the array, and moving the pointer pointing to the smaller element, doesn't work?
I don't think it works... We chop off anything off the left (!) if the sum so far is negative, but we fail to consider if chopping the same number off the right would be better; For example: (100 : -1M : 1 : 1 : 1 ) This algorithm will see that at index 1 we have -999K and it will chop (0:1) off, and leave us with max sum = 3.
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.
@@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 :)
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
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.
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
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.
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;
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
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!👍
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
@@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
but if all nums are negative, then the max sum would just be the first value. because you will not get any larger sum if all the numbers are negative. so just simply return the first value.
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).
Coming up with Kadane's algorithm intuitively is not an easy feat, especially in an interview. I think it would be better to show how to come up with divide and conquer/ recursive solutions and memoize them.
IMO divide and conquer for this algorithm is harder to implement than kadane's. I just did both methods on leetcode. Much easier to make mistake there.
I thought this was a simpler way to write it, def maxSubArray(self, nums: List[int]) -> int: maxVal = nums[0] for i in range(len(nums)-1): nums[i+1] = max(nums[i+1], nums[i] + nums[i+1]) maxVal = max(nums[i+1], maxVal) return maxVal
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
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
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.
This still works since it will reset cursum to 0 at each index, for an array with only negative numbers the maximum subarray would only be one number, the one that is the largest
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
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.
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
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 ?
What if all the elements in the array are negative? The problem can be solved using Kadane's algorithm, check the java solution below: class Solution { public int maxSubArray(int[] nums) { int globalMax = nums[0]; int currMax = nums[0]; for (int i=1; i globalMax) { globalMax = currMax; } } return globalMax; } }
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
This problem is ridiculous. More math than coding challenge. And the ultimate efficiency is so arbitrary, b/c I've never seen any real world scenario asking anything like this _that also has a large enough set to warrant optimization_.
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.
This solution is not accepting by Leetcode so i made few changes class Solution: def maxSubArray(self, nums: List[int]) -> int: maxsum = float('-inf') CurrSum = 0 for no in nums: CurrSum = max(no, CurrSum + no) maxsum = max(CurrSum,maxsum) return 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.
@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)
Ok but the issue I see with this, or at least your explanation, is what if the array is [-5, -10] for instance. Now you get rid of the -5 since it's negative as you say, but the -10 is even more negative
save more time -> class Solution: def maxSubArray(self, nums: List[int]) -> int: maxsum = nums[0] currsum = 0 for n in nums: currsum += n if maxsum < currsum: maxsum = currsum if currsum < 0: currsum = 0 return maxsum
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
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.
Interviews are basically about testing how much time someone spent studying these optimal solutions. Who could come with this on their own if they have never seen the optimal solutions before
To be honest with you, after I've watched your explanation I didn't understand why it was working. Then I watched another video about Kadane's algorithm and I understood that fine. Then I broke down both solutions - even though the values of `currentSum` and `maxSum` are equal for both algos, I still don't understand why your solution is working, which is shameful of me and ridiculous.
The "if (curSum < 0) curSum = 0" is what's super confusing about this problem to me and had me wonder "Wait, what about a list with all negative numbers?"
The multiple insights required to understand such a simple line: * This line essentially "restarts" the substring count from this number. Settings it to 0 is like having done no prior computations. * It will not make 0 the highest number, overriding highest negatives. * Negative maximums will still be found, but they will not include (be summed with) ANY other number in the list. This is because any other number, if positive, would by itself be a higher value. * Any other negative number, by itself, is the highest of all negative number combinations. * Even if the value is negative, and will not be compounded with any other number, it will still be added to our consideration as a solitary (non-summed/combined) max number via the max() call, so long as we never initialized our maxTotal to 0 (because that would take precedent as being higher).
🚀 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!
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)
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
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!
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
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
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.
neetcode please return making videos with this keyboard.. I really get relaxed from this. Even if I solved this, I see the typing part! :>
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)
but where is the condition to remove the negative values
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
This won't work... It will add up n to curSum twice
@@geraldo_silva it won't, test this entire code.
cursum = 0
maxsub=nums[0]
for n in nums:
if cursum < 0:
cursum = n
else:
cursum += n
maxsub=max(maxsub,cursum)
print(maxsub)
I started doing LeetCode for the first time yesterday.... I have a six star in Problem Solving on Hackerrank and it just threw me over a cliff and smashed my organs on this Two Sum problem... My first problem on Leetcode was adding two numbers and then it jumped to this Two Sum
Could someone explain why the two-pointer approach, where one pointer starts at the beginning and the other at the end of the array, and moving the pointer pointing to the smaller element, doesn't work?
amazing,
could you please make this q with divide and conquer?
holy.. I couldn't even come up with the cubic solution when tried to solve it.. Like HOW NAIVE Can ONE GET!! ??? :>>>
Thank you so much for your videos! They've been exceptionally helpful.
So this is just like the stock trading profit maximization problem
Why are you making curSum =0, because max sum can be negative also right?
Everytime a see this as Easy question i die a little inside
This was actually upgraded recently to a medium... so don't worry we can die a little less together. We're not crazy
beautiful explanation as always. Thank you
Wow. This is actually genius.
The question says to try 'divide and conquer'?
what if all elements were negative in the whole array ?
wtf I would never come up with this in a million years
Can you show the DP way of solving this?
what if the edge case of all negative numbers, is empty sub-array allowed ?
I don't think it works... We chop off anything off the left (!) if the sum so far is negative, but we fail to consider if chopping the same number off the right would be better; For example:
(100 : -1M : 1 : 1 : 1 )
This algorithm will see that at index 1 we have -999K and it will chop (0:1) off, and leave us with max sum = 3.
It should still work in that instance. We set the maxSub to 100, and as we continue along, that 100 is being compared against the 3 at the end.
If all the elements are negative, your last approach will fail.
hey what if the whole array is negative.. will it work??
what if all numbers are negative
maja aa gya
What is the difference between "for n in nums " and "for n in range(len(nums))"? Can anyone help?
The second one will give you the index, the first will only give you the actual values.
@@NeetCode Thank you so much!
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?
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.
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}")
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
ruclips.net/video/yBCzO0FpsVc/видео.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
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
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
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;
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
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
This is now a Medium
yes, how?
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!👍
Love the way you explain things super easy to follow along
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
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 dont think this solutioin work if all the numbers in the Array are negative !!! as u making it ZERO.
but if all nums are negative, then the max sum would just be the first value. because you will not get any larger sum if all the numbers are negative. so just simply return the first value.
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.
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).
Coming up with Kadane's algorithm intuitively is not an easy feat, especially in an interview. I think it would be better to show how to come up with divide and conquer/ recursive solutions and memoize them.
Exactly
IMO divide and conquer for this algorithm is harder to implement than kadane's. I just did both methods on leetcode. Much easier to make mistake there.
I thought this was a simpler way to write it,
def maxSubArray(self, nums: List[int]) -> int:
maxVal = nums[0]
for i in range(len(nums)-1):
nums[i+1] = max(nums[i+1], nums[i] + nums[i+1])
maxVal = max(nums[i+1], maxVal)
return maxVal
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.
what if there are only negative numbers in the subarray ?
thats what im thinking
This still works since it will reset cursum to 0 at each index, for an array with only negative numbers the maximum subarray would only be one number, the one that is the largest
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
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.
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
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 ?
Thank you Sir. I have made a silly mistake in this problem now it's clear.
Another possible problem is returning the range of the subarray instead of the sum, then we would have to keep track of more stuff
More intuitive solution:
def maxSubArray(nums) :
global_max = nums[0]
curr_sum = nums[0]
for value in nums[1:]:
curr_sum = max(value, curr_sum+value)
global_max = max(global_max, curr_sum)
return global_max
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
best_combination_sum = -math.inf
current_potentially_best_combination_sum = 0
for num in nums:
previous_winner_with_new_num = current_potentially_best_combination_sum + num
current_potentially_best_combination_sum = max(previous_winner_with_new_num, num)
best_combination_sum = max(current_potentially_best_combination_sum, best_combination_sum)
return best_combination_sum
What if all the elements in the array are negative?
The problem can be solved using Kadane's algorithm, check the java solution below:
class Solution {
public int maxSubArray(int[] nums) {
int globalMax = nums[0];
int currMax = nums[0];
for (int i=1; i globalMax) {
globalMax = currMax;
}
}
return globalMax;
}
}
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
This problem is ridiculous. More math than coding challenge. And the ultimate efficiency is so arbitrary, b/c I've never seen any real world scenario asking anything like this _that also has a large enough set to warrant optimization_.
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.
maxsub will return sum of maximum subarray, and not slice of list which constitutes maximum subarray .... right/?
This solution is not accepting by Leetcode so i made few changes
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxsum = float('-inf')
CurrSum = 0
for no in nums:
CurrSum = max(no, CurrSum + no)
maxsum = max(CurrSum,maxsum)
return maxsum
paaji tusi great ho
You should have kept maxSum instead of maxSub as it would create confusion
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
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.
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.
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)
I just don't know how is your thought process from a two-pointer sliding window drawing to such a solution. It seems completely irrelevant.
This was very helpful, please make a Divide and conquer solution for this too.
me crying and laughing at the same time
This solution wouldn't work for the case where all numbers in the array are negative, would it?
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 dont understand why if current sum is negative then it doesnt contribute anything can you explain more on this issue?
Please use dark mode
Does this solution work if the array contains only negative integers?
Given an array of just negative numbers wouldnt the highest be 0 instead of the biggest number out of all the neg numbers
This is a wrong solution, test on nums=[-2,-1], for example.
The code is very efficient so efficient my monkey brain cant keep up with whats happening in the code lmao
Ok but the issue I see with this, or at least your explanation, is what if the array is [-5, -10] for instance. Now you get rid of the -5 since it's negative as you say, but the -10 is even more negative
in the end the loop, he compared the max and the left to avoid this case
i though there is no intuition behind this algo, i just need to memorize it, but you changed my mind
save more time ->
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxsum = nums[0]
currsum = 0
for n in nums:
currsum += n
if maxsum < currsum:
maxsum = currsum
if currsum < 0:
currsum = 0
return maxsum
the only question i have
how the fuck you got the same runtime in the last two submit 😂😂😂😂
crazy algorithm, note you can also just set the maxSub = -math.inf initially so it follows the pattern of other max value problems.
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 ?
You are ignoring the negative sum, what if the max sum is a negative one
Thanks, great explanation and good visuals.
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.
Interviews are basically about testing how much time someone spent studying these optimal solutions. Who could come with this on their own if they have never seen the optimal solutions before
It sucks that nobody will get hired if they are not Kadane or if they didn’t go on leetcode or watch neetcode before
To be honest with you, after I've watched your explanation I didn't understand why it was working. Then I watched another video about Kadane's algorithm and I understood that fine. Then I broke down both solutions - even though the values of `currentSum` and `maxSum` are equal for both algos, I still don't understand why your solution is working, which is shameful of me and ridiculous.
The "if (curSum < 0) curSum = 0" is what's super confusing about this problem to me and had me wonder "Wait, what about a list with all negative numbers?"
The multiple insights required to understand such a simple line:
* This line essentially "restarts" the substring count from this number.
Settings it to 0 is like having done no prior computations.
* It will not make 0 the highest number, overriding highest negatives.
* Negative maximums will still be found, but they will not include (be summed with) ANY other number in the list.
This is because any other number, if positive, would by itself be a higher value.
* Any other negative number, by itself, is the highest of all negative number combinations.
* Even if the value is negative, and will not be compounded with any other number, it will still be added to our consideration as a solitary (non-summed/combined) max number via the max() call, so long as we never initialized our maxTotal to 0 (because that would take precedent as being higher).
the maximum sum in an array with negative numbers is the number with the maximum value
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