Maximum Subarray - Kadane's Algorithm -- Leetcode 53

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

This might be the most asked coding question ever! Seriously, it comes up ALOT!! Kadane's algorithm is a bottom-up dynamic programming solution to the max sum subarray problem, #53 on leetcode. Drop a like if you found this helpful! :)

[vanlepthien]

You said that you wanted to get the subarray with the maximum sum, but you got the maximum sum, not the subarray. Either you misstated the problem or you botched the solution.

[sanskritclub]

I prefer this for an interview than sticking a <div> to top while scrolling!

[nk]

So this is more like the max sum when navigating left to right. I thought you were looking for the subarray that produced the max sum which would include knowing when to not include numbers at the start of the sum list because they decrease the sum more than they add to it.

[PostMeridianLyf]

I love these. Your explanations are very accurate and simple

[-]

Luv ur shorts just to point and a lot of info 👍👍👌

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[shreayankanjilal]

One thing I do not understand is why even bother putting max_sum -ve infinity. It will be assigned curr_sum after the first comparison. Is it like a readability thing?

[avdhootgole]

I was procrastinating to search this, I got this in my feed😅

[kyoai]

You say "We want to find the array that has the maximum sum", yet you are not returning the max sum subarray, you are returning the max sum number.

[george]

There are 2 issues there:
1. What if all numbers are positive? Then you get the sum of the array, not subarray.
2. What if all numbers are negative? Then you just hardcode the current sum to and this way you will get the biggest number(negative) from the array.

[wxeddd]

Would you just nullify current sum if it gets negative and do not include those numbers into array? For an example [-2, 7, -8, 7, -3, …], where 7-8=-1. Would be grateful if you answered

[rahuldwivedi]

Why do you need to initialise max_sum with -Infinity when you know you can return 0?

[lucanthony]

if the sign of -2 was positive, will the max_sum still be -infinite?

[aarondrew]

Can sliding window algorithm also be used for solving maximun subarray?

[mikemayer]

These types of knowledge test that only check to see if you know the right terminology drive me up a wall. Clearly anyone who understands the problem domain here well realize the better solution is to filter to keep only the positive values.

[AtticusHenry-cl]

How do we know to get rid of -2? If all the other numbers were negative it could be the largest sub array?

[waffle]

what do you do if you need to return the sub array instead?

[RickyRicheRebelle]

is this a language barrier ? cuz a "subarray" for me is just a literal sub array derived from the original array, no matter the element selection order, so for me the max subarray would be -2, 7 and 4

[hlubradio]

Just to let you know I'm also implementing it in C++ as well