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 :)

[@debangan]

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

[@techdose4u]

😅

[@YisName]

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

[@techdose4u]

Thanks :)

[@RudraSingh-pb5ls]

I don't think so ! He explained the algorithm in a good manner but that's rote learning.

[@RudraSingh-pb5ls]

He should have told us how that algorithm was built on what mathematical basis Kadane got the intuition for this problem and developed an O(n) solution

[@anjalisingh-sx5ct]

@@RudraSingh-pb5ls intuitive approach would be for each element compare it with all the elements on its right side.. (2 for loops)...add them if(sum>0)...this would take 0(n^2)
Which is very similar to kadane algo(we taking 2 pointers one for adding the elements and other for finding the longest subarray sum)is similar to this n reduce the runtime...

[@RudraSingh-pb5ls]

@@anjalisingh-sx5ct I know what is kadanes and how it works but the way you guys are explaining is the worst. You just telling me how to do instead of why ?
So the question isn't how , question is why !

[@alexpadilla5741]

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.

[@techdose4u]

👍🏼

[@Sachin_Alam]

true!

[@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.

[@techdose4u]

Thanks :)

[@subham5785]

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

[@techdose4u]

Nice :)

[@Usurperhk]

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

[@techdose4u]

Thanks

[@rohiteshkumarjain7772]

Although you have only 12.2 k subs, pls don't stop making videos, have patience and keep making such videos, it will take time but you will surely reach 1M subs soon. Don't stop, if you feel your videos are not making money, make videos as a charity to the students.

[@techdose4u]

Sure man :) Even though I don't earn much through CZcams, but by making videos I get to learn as well. Also, teaching is my hobby. So, I will continue :)

[@AdityaRaj-bn3ht]

@@techdose4u You have helped me a lot. You explain the topic very well. Hats off man for your effort.

[@nishant5249]

@@techdose4u thanks sir please keep going... we need your videos

[@binod3204]

@@techdose4u And here it goes...... You`ve now 65.6k subscribers :)

[@techdose4u]

Stay connected with us ☺️

[@expansivegymnast1020]

Very simple and it works THANK YOU

[@alishasingh4382]

Thank you, for this nice and clean explanation

[@sarfarazhussain6883]

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.

[@vitaliitomas4057]

MSF - Max So Far
MEH - Max Ending Here

[@sarfarazhussain6883]

@@vitaliitomas4057 I know that.

[@hodgsontetteh4058]

if we add have a running sum rs and we claim its part of the maxsum sub array then if we add b :rs+b = maxsum but we notice that maxsum is less than b then rs is negative if so then b = rs +maxsum where b is the maxsum then ou initial claim that rs is part of the maxsum array is false so we drop it in simple word if rs+b is less than b then rs will always weigh us down so we drop it

[@rahuls331]

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.

[@techdose4u]

I mean to say that kadane's algo works when atleast 1 number is positive (I presented it in an ambiguous way). If you have all negative numbers then kadane's was taking max_ending_here = 0 which would never get updated because all numbers are negative and output would be 0. I hope you get it now.

[@Dankman3]

Clear and informative as usual. Good job.

[@techdose4u]

Thanks :)

[@rushikeshborse1994]

Magnificent implementation of Algorithm..!!
Keep it up👍

[@techdose4u]

Thanks :)

[@gundasreedhar327]

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

[@rajendransubramanian6813]

Thanks for the good explanation, but how did you select the contiguous elements from 4 to 5, i mean the index starts from 2 to 6

[@ganesh_130]

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

[@techdose4u]

Great ❤️

[@ajaywadhwa3398]

how did you get the intuition for that ?

[@salonimaniyar3943]

Perfect Solution I found.. Thank you so much 👍

[@sunilpatel6542]

Hi can I know why you modified existing also what kind of issues are you trying to solve?

[@consistentthoughts826]

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

[@vivianpaul2078]

goodjob

[@Nainalarenukadevi9196-dh8rz]

how to print that array

[@ashwinraj8918]

The best explanation of Kadanes Algo!!

[@techdose4u]

Thanks

[@PramodYadav-dr9vq]

how did you decide the first element of subarray

[@ambrish8144]

excellent video Straight to the point thank you

[@techdose4u]

Welcome :)

[@adhaarsharma753]

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

[@techdose4u]

Great :)

[@MohamedAshraf-ri9wb]

how to track using left and right pointer to get that array

[@adityarathi3420]

Thanks sir :-)
Simple code snippet for easy understanding : C++
int maxSubArray(vector& 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;
}

[@vishnusivan9382]

what is auto num?

[@adityarathi3420]

@@vishnusivan9382 if you use Java it's for (int num: nums) {}

[@s50498]

There is one queston with respect to the above concept. For example if I have arr = [1, -2, 3], then manually i know that
subrray with index 2 i.e [3] will hold the maximum sum. I am speaking with respect to contagious array. Subarray by taking the third element is also contagious according to me. If i run the above mentioned concept code, I get the result as 1, which means first element of the array but result from manual approach is not same.
Can you please explain me where I am lacking or do i need better understanding of contagious array.

[@newgamer4669]

Well described!! THANKYOU

[@tekno864]

Thanks for the video, I was trying to solve this problem for 1 day

[@killeraloo3247]

mast video banai, bhaiya, sab samajh aa gya.

[@hanumanthram6754]

Good explanation. Got more clear to me.!

[@tuhinkumardolai9836]

helped a lot to understand... Thanks sir

[@saicharan-lj2bz]

This Helped. Thank You.

[@techdose4u]

Welcome :)

[@MadForCs16]

Best explanation so far.

[@techdose4u]

Thanks :)

[@Shashank0002]

Sir which app you use for making these videos??

[@ashutoshsinghpatel196]

You are GOD in explaining algorithms 🙂

[@adnanjmi21]

Useful tutorials , which sw/tool use for writing this

[@arjunkhanna1803]

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

[@riteeshbommaraju]

Beautifully Explained !! The best explanation of Kadane's Algorithm !! Keep it up mate !!

[@techdose4u]

Thanks :)

[@shaswatsingh]

Which software do you use

[@shubhamjaiswal9314]

if (max_ending_here < 0)
max_ending_here = 0;
why this is also working

[@sehejwahla5437]

Great content bro !!

[@theyoutubespecialist9004]

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

[@techdose4u]

Thanks 😊

[@jayantakumarroy543]

tum jo aaye zindagi mei baat bann gayi.awesome explanation

[@techdose4u]

Thanks bro :)

[@patilsoham]

Great tutorial...Thank You

[@techdose4u]

Welcome :)

[@activecoder1844]

What is the default value of int_min?

[@suman6327]

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;
}

[@techdose4u]

👍

[@nagavarma7006]

Man outstanding solution my brain cant even think of it

[@techdose4u]

Now you know it :)

[@nagavarma7006]

@@techdose4u Clean explanation Obviously Yes

[@techdose4u]

:)

[@koyavasudhalakshmi2073]

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

[@techdose4u]

👍🏼

[@harshit4190]

how do cal indices with same logic? please explain me a bit of it

[@techdose4u]

???

[@Relaxingmusic-tw4qn]

bro if possible can u 1st make recursive version + memorization of kadance ,Longest common subsequence,and few more parent question its helps us to develop logic and how to use dp in these question.
and btw ur explanation is super awesome and easy to grasp thanks brother :)

[@techdose4u]

On my way. Currently doing it.

[@l.paulsonraja4036]

Best Video for Kadanes algorithm.

[@techdose4u]

Thanks 😊

[@rishurana9655]

Great work sir but what is the intuituion behind this algo?

[@kshitijgaur9635]

Amazing explanation !!!

[@techdose4u]

Thanks

[@porassingh4904]

what if we had to return the maximum sub array? for that we will have to use n^2 approach right?

[@techdose4u]

No. You can maintain a left window pointer which will update whenever the current sum falls below 0

[@osamaraza6001]

@@techdose4u could you please elaborate it more in detail?

[@tungtruong5904]

This algo is awesome, the author is supper hero.

[@techdose4u]

🤗

[@nishalgoud2286]

How to keep track of position of contiguous subarray using pointers?

[@Vsumit17OG]

Nice,
But for kadanes algo there is condition of atleast one positive number must be present in array.
So, this problem will solve easily by kadane algorithm.

[@neojai3514]

we can use sliding window algo here to get the exact subarray as well

[@jordanguada4354]

Great logic, I'm currently using this to learn for my Microsoft Interview.
Thanks alot man, practiced and memorized this algorithm. I'll try to do it daily.
Cheers from Florida, keep up the videos. You got a sub my man.

[@techdose4u]

Nice :)

[@shouryatrivedi2172]

how can we keep trackof subarray indices side by side??? i mean how would iteration take place?

[@techdose4u]

If you find a max value then just save the ending index. After kadane's is done, just parse the array from the saved index in reverse order. Stop when sum value is same is maxSum. That index is your left index :) Congrats, you have now found the window.

[@vedantmondkar9963]

@TECH DOSE can u tell why this problem is there in your DP Playlist? How is it related to DP

[@techdose4u]

It's a DP algo.

[@vedantmondkar9963]

@@techdose4u So a DP algo can be made without using extra space right??

[@atharvprasadparanjape6140]

How to use INT_MIN in Python 3

[@BurhanAijaz]

how to get the exact subarray if required?

[@agileprogramming7463]

So neat!!

[@techdose4u]

:)

[@sehejwahla5437]

I dont earn atm, but when i start earning, I'll make sure to support ur channel

[@techdose4u]

Thanks for your support :)

[@sakshirana1912]

can u explain why we check this condition if(meh

[@blindprogrammer]

the best explanation so far found on any source!

[@techdose4u]

:)

[@prajwalsrivastava1983]

Very well explained sir

[@prateekaryan1020]

In the brute force approach, you said it will be the order of O(n^2).
pseudocode for the brute force approach :
sum=0
for (i=0 to n)
for (j=i to n) //two loops for finding all substrings.
max(sum,sum(i to j)) // sum of that substring.
I think this brute force approach will take O(n^3) order.
Correct me, if I am wrong :)

[@BarkaDog]

Nope it will be O(n^2)

[@VasuVandankodakandla975]

Yes, it is n3.

[@Rahul-uk4su]

Yeah even i got this

[@spoiler407]

Easy to understand.
arr=list(map(int,input().split()))
maxi=arr[0]
sumi=0
for i in arr:
sumi+=i
if sumi

[@Salmanul_]

Thanks!

[@MunniDivya]

thankuu it worked for -ve numbers alsoo

[@techdose4u]

Welcome :)

[@gurnoorsingh2954]

Like these 27 people are even humans?
This is the easiest approach I have ever seen for this algorithm and tech dose have explained it in the best way

[@techdose4u]

Thanks

[@harshmanola563]

@@techdose4u Possibly your code doesn't work correctly for multiple test-cases (TCs).

[@coder2684]

Nicely u explained

[@rishiAura]

can any one provide here this algorithm implementation in python....?

[@naturelover5824]

Initially "msf" is 0(zero) you said. In the second if condition 0(zero) is not less than -2 know. Then second if statement also fails for the first loop. But you explained msf becomes -2 after 1st loop. How is it possible?

[@jjbrotherscreation3267]

Bro this Playlist is enough for clearing MNC Coding interview pls reply.
Very well explaination bro. I loved it.

[@techdose4u]

It's good but not enough. Try to cover as much as you can from all my playlists.

[@ashwikraoalladi3320]

👌👍 excellent sir

[@nutankumari9977]

Nice explanation with all possibilities

[@techdose4u]

🙂

[@shrutigupta9319]

Best Explanation!!

[@techdose4u]

Thanks

[@santasingh9045]

great explanation sir!!

[@techdose4u]

Thanks :)

[@ThanosAtWork]

Bro best one keep making videos ☺️

[@techdose4u]

Thanks :)

[@vishwanathhosmane3834]

Sir from which place you belongs to? Plz reply

[@saisanthosh8370]

how to use int_main in python

[@palakurthybadrieshwar9999]

i did not understand what is INT_MIN please reply me

[@vitaliitomas4057]

You are a life saver. Any advice how do I implement primes into it? Also subbed

[@techdose4u]

Primes meaning ?

[@vitaliitomas4057]

@@techdose4u Number that can be divided only by themselves and 1, i.e 2, 3, 5, 7, 11 etc. I have to find largest subarray under the condition that absolute value of every number of it is prime number.

[@namanvohra8262]

The best explanation out there

[@techdose4u]

Thanks

[@osamaraza6001]

@@techdose4u Kindly guide how to print the elements of the desired max subarray

[@himanshudhyani6076]

How to print max sum contiguous sub-array?

[@techdose4u]

When you slide and update your max_so_far, just maintain two int variables which will store the index where you are updating your value. At the end of parse, your index values stored will give the window starting and ending index. I hope you got it :)

[@himanshudhyani6076]

@@techdose4u Thnx :)

[@b.sainathreddy4567]

can u explain how to find kth largest contiguous sub array instead of largest contiguous subarry using kadanes alogrithm

[@techdose4u]

Can you further explain the statement and give the problem link.

[@b.sainathreddy4567]

@@techdose4u www.geeksforgeeks.org/k-th-largest-sum-contiguous-subarray/
this one :)

[@subratamondal7056]

When should we update the pointers?

[@techdose4u]

You need to check when value falls below min.

[@villagevlogger4615]

Easy Explanation

[@myriad1703]

nice explanation

[@mukulkirtiverma2781]

Super video! I applauded for ₹40.00 👏

[@techdose4u]

Thanks for your support :)

[@sidkapoor9085]

shouldnt msf be array[0]?

[@anupamajayakanthan4402]

Hi Bro its an amazing explanation..... Can u also explain the same in case of a circular array

[@techdose4u]

I will try later

[@azizulhakimsaif1420]

amazing

[@nmkyuppie]

Thanks man 😎

[@techdose4u]

Welcome :)

[@osamaraza6001]

@TECH DOSE Kindly guide how to print the elements of the desired max subarray

[@techdose4u]

Just track the starting index and window size. That's it

[@jasmeenkaur6001]

Best 😇😇😇 explanation

[@techdose4u]

Thanks :)