Kadane's Algorithm in 2 minutes | LeetCode Pattern

kin's algorithm a problem solving technique that is used to efficiently solve the maximum subarray problem what's the maximum subarray problem you're given an array and you need to find the subarray with the maximum sum a sub array is a continuous sequence of

elements within the array if the array contains only positive numbers the solution is straightforward the subarray with the maximum sum would include all elements in the array but the challenge arises when the array contains negative

numbers making it tricky to decide which elements to include for example in this array the subarray with the maximum sum is 4 - 1 2 and one with a total sum of six The Brute Force approach to solve

this problem is simple check every possible suray using nested Loops calculate the sum for each sub and keep track of the maximum sum while it works this approach has a Time complexity of order of n Square which is too slow for

large inputs K this algorithm optimizes this process to run in order of end time by dynamically deciding whether to extend the current sub aray or start f with a new subay if adding the current element to the subay increases the sum

extend the subay otherwise it start fresh with the current element this shows the sum remains as large as possible let's walk through four possible scenarios for each element if the sub sum is positive and current

element is also positive extend the subarray as adding the current element will increase the sum further if the sub sum is negative and current element is positive start a new subarray with the current element as is greater than

adding it to a negative sum if the sub sum is positive and current element is negative extend the sub as the overall sum will still be larger than starting phrase if the sub sum is negative and the current element is also negative

start a new subay to avoid reducing the sum even further here is how the K algorithm looks like in code here I'm using Java but you can find a code for other popular programming languages in my GitHub repository called awesome lead

code resources it start by initializing variables to track the current s sum and the maximum sum current sum tracks the sum of the current subay weiz it to the first element because that's the only subay we have at the start Maxum

variable keeps tracks of the highest some s so far itate through the array starting from the second element decide whether to start a new sub array or extend the current one by comparing the current element itself and the current

element added to the previous s sum update the current sum to the maximum of these two then update Maxum if current sum exceeds it after completing the loop return the maximum sum found here are some more liquid problems you can

practice using this approach you can find these problems on algomas doio simply head to the practice space search for this pattern or use the filter drop down and start practicing on this platform you can Mark problems as

complete or restart them for later revision you can also find the links to get and YouTube solutions for each problem if you want to check out the full lead code patterns playlist click here don't forget to like subscribe and hit the Bell icon so you won't miss my

future videos thanks for watching and I will see you in the next one