Kadane's Algorithm and Its Proof - Max/Min Sum Subarray Problem

In this video, you will get the optimum solution to the maximum/minimum sum subarray problem: The Kadane's Algorithm. The problem at hand is simple. Given an array of integers, say [-1, 1, 3, -2], find the subarrays with the maximum and minimum possible sums (for the given example: max=[1, 3], min=[-2]). Kadane's Algorithm solves this problem with a nice O(n) time and O(1) space complexity. A variation of this problem is when you are trying to find the maximum/minimum sum subarray with at least k elements. Again, a slightly modified version of Kadane's Algo can be used in solving it. Finally, we will prove the correctness of Kadane's Algorithms.

When all integers in a given array are positive, you can use the much simpler Sliding Windows Technique. For arrays with negative numbers, you can modify it to be all positive numbers and then apply the sliding window technique, but that requires extra processing; hence it is not the optimum solution. I have a separate video discussing the sliding window technique in depth along with various sample questions, and you can find the link to it below.

Kadane's Algorithm uses optimal substructures to solve the max/min subarray sum problem. Each max/min subarray ending at each index is calculated using the max/min subarray ending at the previous index. You can say that this is an accumulation function with some additional rules. As a result of this, it is one of my favorite examples of Dynamic Programming. In the video, I will explain how Kadane's Algorithm is an optimal substructure problem using a basic animation.

In the video, you will find the solutions to the following questions, as well as their time and space complexities:
* Medium Difficulty: Kadane's Algorithm: Given an array of integers, find the subarray with the maximum/minimum possible sum.
* Medium Difficulty: Sliding Window on Kadane's Algorithm: Given an array of integers, find the subarray with the maximum/minimum possible sum with at least k elements.
* Hard: Prove Kadane's Algorithm: Prove the correctness of Kadane's Algorithm.

Solution code to examples are available on:

If you can read the article version of this video at:

My "Sliding Window Technique" video that can be applied similar circumstances:

My "Algorithms" Playlist for all other algorithm questions & answers:

- - - - - - - - - - -

[QuanticDev]

4:48 I had "exponential complexity" on screen which should actually read "quadratic (polynomial) complexity" instead.
14:06 Time complexity should read O(n). Asymptotically O(kn) is equal to O(n) so we always write O(2n), O(3n), etc. as simply O(n).
15:12 "Sum(x)(i+1) = Sum(x)(i) + El(i)" is a typo. Instead, it should read "Sum(x)(i+1) = Sum(x)(i) + El(i+1)". Keeping track of indices is hard!
15:32 Another typo with the indexes. Second row should read "MaxSum(i+1) = Max(MaxSum(i) + El(i+1), El(i+1)) ...." and so on.

[tejasghone]

Awesome explanation!! Your sliding window and this kadane one are so far the best videos iv seen on youtube for these topics.Thank you and hope to see more videos in future!

[blasttrash]

The best explanation on youtube so far. Thanks

[undefBehav]

5:00 O(n^2) exponential değil, polynomial time complexity kategorisine gider. Çoğu NP problem için düşündüğümüzde de 'ridiculous' değil, aksine oldukça 'kabul edilebilir' bir time complexity olduğunu görürüz. Çoğu dinamik programlama probleminin lower bound'u da eninde sonunda bir memotable üzerinde işlem yaptığımızdan n^2 veya m*n gibi değerler olarak karşımıza çıkar. Kadane's algorithm senin de videonda söylediğin gibi optimal substructure'ları leverage ettiğin için bu kategorinin bir alt kümesi.

'Unlimited input' bazında brute force'u inefficient olarak değerlendirmeni de anlayamadım. Kadane's algoritmasında da unlimited input olması durumunda unlimited time ve space kullanmak durumundasın?

[shardator]

Quick note: AFAIK O(2n) is the same as O(n). In general, O(a*n^p + b*n^(p-1) + c*n^(p-2) +...+ y*n + z) = O(n^p)

[utkarshtiwari]

Nicely explained, but I saw on your website. You start by declaring 'max sum = 0', how about finding "maximum sum" for an array of all the -ve integers. I believe in this case the 'current sum' will never be grater than 'max sum' and thus the result will always be 0, which would be wrong.