AMAZON INTERVIEW QUESTION | Maximum Subarray (LeetCode problem 53)

Day 23 of the 100 Days of LeetCode

Hey there! My name is Michele “Mike” Catani and I’m just somebody who loves to program.

Here on my channel, I’m going to be posting solutions to LeetCode problems every day for the next 100 days excluding Sundays! The only way to get better at programming is by approaching it like anything else… practice, practice, practice!

[KingQuixote]

It took me a while to see why this code works, so here's an explanation in case others are confused.
Let A[j] denote the best subarray whose final element has index j. Then A[j+1] is either just the (j+1)th element by itself, or A[j] together with the (j+1)th element. (This is not initially obvious but becomes so after a little thought).
In the code in the video, cur, at each iteration, will be equal to the sum of A[j]. Then the line involving 'theMax' simply remembers the largest value of sum(A[j]) as j varies.

[nvm]

this is the most asked question ever imo