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:
* https://github.com/soygul/QuanticDev/blob/master/algorithms/dynamic-programming/kadanes-algorithm

If you can read the article version of this video at:
* http://quanticdev.com/algorithms/dynamic-programming/kadanes-algorithm

My "Sliding Window Technique" video that can be applied similar circumstances:
* https://www.youtube.com/watch?v=jM2dhDPYMQM

My "Algorithms" Playlist for all other algorithm questions & answers:
* https://www.youtube.com/playlist?list=PLlPRnMzqjADqDZFBqdwzbIjf71h8xYs4x

- - - - - - - - - - -
https://twitter.com/quanticdev
https://instagram.com/quantic_dev
https://quanticdev.com