Maximum Subarray (Kadane's Algorithm) - Leetcode 53 - Dynamic Programming (Python)

Please check my playlists for free DSA problem solutions:

Best Courses for Analytics:
---------------------------------------------------------------------------------------------------------

Best Courses for Programming:
---------------------------------------------------------------------------------------------------------

Best Courses for Machine Learning:
---------------------------------------------------------------------------------------------------------

Best Courses for Statistics:
---------------------------------------------------------------------------------------------------------

Best Courses for Big Data:
---------------------------------------------------------------------------------------------------------

More Courses:
---------------------------------------------------------------------------------------------------------

Full Disclosure:
Please note that I may earn a commission for purchases made at the above sites! I strongly believe in the material provided; I only recommend what I truly think is great. If you do choose to make purchases through these links; thank you for supporting the channel, it helps me make more free content like this!

[GregHogg]

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

[galdali]

You can also solve it using divide and conquer:
There are three possibilities:
1. The maximum subarray is entirely within the left half.
2. The maximum subarray is entirely within the right half.
3. The maximum subarray crosses the middle i.e. starts in the left half and ends in the right half.

Solve the first two cases recursively, the last case can be solved in O(1) by utilizing the recursive calls and the time complexity will be T(n) = 2*T(n/2) + O(1) which is in O(n)

For each recursive call, return:
The maximum subarray for the current segment, the total sum of the current segment, the maximum prefix sum of the current segment, and the maximum suffix sum of the current segment.
With this, you can calculate the maximum subarray in each half, the maximum subarray that crosses the middle and the total sum of the array, the maximum prefix sum, and the maximum suffix sum. The time complexity is O(n)

[ggsoldchannel]

Thanks for making dynamic programming videos. I'm learning it right now and your vids are very motivating. Keep it up!

[raenielsaavedra]

Thank you for the very easy to follow video. Although it may be obvious to many who will watch this but the max sub array is actually [-2, 7, 4] I think its because of the resetting to 0 thus no longer considering -2 as an option that's why -3 was chosen instead.

[tejas]

This is a pretty hard problem. One cannot come up to Kadane's Algorithm on it's own unless he / she have spent at least 5 - 6 Hours on this problem. Unless he / she is a genius.

Many companies ask this problem. I believe most of them are even fine with the Brute Force approach as well (nested loops O(n) solution).

[chethanmungara]

i have a doubt . if cur_sum < 0 why should set cur_sum to 0 again?