Kadanes algorithm | Longest sum contiguous subarray

This video explains the modified version of kadane's algorithm that works for both positive as well as negative values in an array. This algorithm is used to find the largest sum contiguous subarray from a given array. Kadanes algorithm is one of the most common question in programming interviews. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[YisName]

I have seen several explanations. But this one is best.

[alexpadilla]

The variable names make it more confusing than it needs to be (at least for me it did), renaming to sum & result would make it easier to understand.
Sum keeps track of max (sum of prev numbers + curr or curr by itself). And then result just keeps track of the largest sum you’ve encountered.

[debangan]

When you are so bored coding that you name your variable 'meh'

[sarfarazhussain]

Hi,
Can you please explain the thought process behind the solution? I mean how did you come up with 'msf' and 'meh'? A detail explanation behind the intuition will be helpful.

[adityarathi]

Thanks sir :-)
Simple code snippet for easy understanding : C++

int maxSubArray(vector<int>& nums) {

int max_sum = INT_MIN, curr_sum = 0;
for(auto num: nums){

curr_sum += num;
max_sum = max(curr_sum, max_sum);
if(curr_sum < 0) curr_sum = 0;
}

return max_sum;
}

[ganesh_]

Thank sir I have learnt whole DSA with strong understanding from your channel

[adhaarsharma]

This is my favourite Youtube channel for Coding along with mycodeschool.

[PrafulPrasad]

Dudeee I have scraped the entire internet to understand this algo and till now yours was the best, I have completely understood it now, you have not overcomplicated things or undercomplicated it to make it seem tad easy, you have kept the difficulty just perfect.

[rahuls]

At 1.26 you have said that kadane algo only works on positive array. For a positive array, entire array is a longest sum contigous block. Considering subarray can also be the whole array.

[Usurperhk]

Best explanation of Kadane's algorithm, Good job TECH DOSE!!!

[consistentthoughts]

For Python coders:

def maxsubarray(arr):
n = len(arr)
curr = arr[0]
final = arr[0]
for i in range(1, len(arr)):
curr = max(arr[i], curr+arr[i])
final = max(curr, final)
return final

[spoiler]

Easy to understand.
arr=list(map(int, input().split()))
maxi=arr[0]
sumi=0
for i in arr:
sumi+=i
if sumi<0: # if left hand is -ve then adding it to right side futher reduces it.
if maxi<sumi:
maxi=sumi
sumi=0
else: # if left hand side is +ve then it can add to right side (elements).
if maxi<sumi:
maxi=sumi
print(maxi)

[arjunkhanna]

for better understanding read the conditions as : a[i] > meh & meh > msf

[theyoutubespecialist]

Trust me buddy, there can't be a better explanation than this! ❤️

[subham]

Great explanation, I was going round and round many videos since last 2 hours. Finally got it

[suman]

Fantastic explanation !!

Simple code snippet for easy understanding :

private int solve(int[] arr){
int prefixSum = 0;
int max = Integer.MIN_VALUE;

for (int elem : arr) {
prefixSum += elem;

prefixSum = Math.max(prefixSum, elem);
max = Math.max(max, prefixSum);
}

return max;
}

[jayantakumarroy]

tum jo aaye zindagi mei baat bann gayi.awesome explanation

[gundasreedhar]

no one can explain it like u.. god bless u

[alishasingh]

Thank you, for this nice and clean explanation

[koyavasudhalakshmi]

I have seen many videos, but this one solved my doubtssss🙏🙏🙏🙏🙏