Maximum Subarray (Leetcode #53 SOLVED)

Maximum Subarray (Leetcode #53 SOLVED) // Do you know how to solve this problem?

The maximum subarray problem on Leetcode (#53) is an interesting coding interview problem that you should include in your coding interview prep.

In this video, I'll show you this coding interview question and answer and walk you through the exact thought process to solve this problem if you see it in an interview at a company like Google or Facebook.

Check out the solution to this coding interview question.

RESOURCES & LINKS MENTIONED IN THIS VIDEO:

YOU CAN ALSO FIND ME HERE

[markos]

this solution won't work if all the numbers are negative will it?

[ngansstudio]

Thank you for explaining really well. At 7:40 if the entire array is negative then the first can be negative

[ricardofilipegomes]

i would argue it is O(N^3) in the brute force, don't forget the sum of the array from i => j is O(N) nested in that loop :)

Amazing job btw

[ThomasRojan]

Excellent explanation of how to arrive at the solution. Thank you

[mallarajes]

what about array contains [ -2, -3, -4, -5, ] and if output expects [-2]. Can we use resetCounter logic ?

[liwaiyip]

Why the brute force is O(n^2) instead of O(n^3)?

Doesn't the sum(arr, j, i) also cost O(n) time?

[vyshnavramesh]

Nice logical thinking. Different from Kadane's. But kinda good to be discussed in an interview.

But for array of all negative numbers, we will have to maintain another variable for storing smallest negative number I believe.

[natashaminer]

You mention that if the first and last element of the array are negative, they will not be included in our subarray. What if our subarray is [-1, -5, -5, -5] or something similar? Then wouldn't our result be -1? (Assuming we are handling negative cases).

[DK-oxze]

Resetting the sum to zero when we encounter a negative number in the array won't work when all the elements in the array are negative. Because then we would want to return the "lowest" negative number. And the problem statement also doesn't mention that all the numbers won't be negative, so we can't assume that.

[vyshnavramesh]

Key point that could be discussed while on interview:
- we are recomputing previous subArrays in the O(n^2) method, which is what to be optimised.
- Optimal method concept: Build the solution from smaller subProblems.

[liwaiyip]

I think there is an intuitive way to show why the nested for loop in brute force approach is O(N^2)
When i = 1, the nested loop executes 1 time
When i = 2, the nested loop executes 2 times
When i = n, the nested loop executes N times
1 + 2 + ... + N = (N *( N + 1)) / 2 = 0.5N^2 + 0.5N = O(N^2)

[KillPhill]

Another excellent video!

Just a heads up, using Red and Green colors (especially for contrasting principles due to human nature tendancies to adhere to subconscious color theory of showing the primary colors in two colors) may not be the best for teaching due to color blindness. I program my apps to minimize color blindness impacts as well as assisted my friend in law school who wanted to become a law school professor on how to teach complex legal theories while I attended law school.

Red and Green combination is the most common color goodness problems. Red and dark blue to cyan might be good compliment. Deep gold and purple is another good pair. And of course, blue and orange is a the most used in advertising for explosion contrasts. Ultimately, you can't please all different types of color blindness, but green and red is a combination that should be avoided in teaching.

[polam]

I believe the brute force answer isn't complete, if you were to have an array [-1, -2] that algo will give you -3 as the greatest sum, tho the answer should be -1 since subarray of size 1 also count

[junigomo]

At first I thougth the problem was to return the whole subarray, in that case, could it be done with the same solution at O(n)? or the complexity increases?,


Thanks for the video, I'm preparing for a in interview

[ByteByByte]

Have you seen this problem in an interview? Let me know in the comments.

[carlreiser]

You can add something like -> return Math.max(...nums) < 0 ? Math.max(...nums) : Math.max(...sumArry) to fix the negative case. Assuming sumArry is the literal sumArry that you built

[treyquattro]

the O(N) solution is Kadane's algorithm. What's the "divide & conquer" approach that Leetcode mentions?

[MilMike]

this problem makes scrambled eggs out of my brain....

[eduriseworld]

aaha "The Four-Hour Workweek"

[sumanth]

WTF is he doing
WTF is he doing
Aah makes sense