Kadane's Algorithm | Largest Sum Contiguous Subarray | Java and C++ | Anuj Bhaiya ✅DSAOne Course #13

Hey guys, In this video, we'll be solving Largest Sum Contiguous Subarray Problem using Kadane's Algorithm.
Practice here: practice.geeksforgeeks.org/
🚀 Follow me on:
Instagram: / anuj.kumar.sharma
Linkedin: / sharma-kumar-anuj
Twitter: / realanujbhaiya
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
🥳 Join our Telegram Community:
Telegram channel: t.me/coding_enthusiasts
Telegram group: t.me/dsa_one
💸 Visit www.educative.io/anuj to avail discount on all courses on Educative!
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The C...
Complete Android Development Playlist: • Android Development Tu...
Hashtags:
#anujbhaiya #dsaone #kadane #algorithm
Ignore these tags:
kadane's algorithm
kadanes algorithm
kadane
kadane algorithm
algorithm
maximum sum subarray kadane algorithm
kadane's
algorithms
kadanes algorithm maximum sum subarray
kadanes algorithm to maximum sum subarray
kadane's algoritm
kadane's algorithm maximum sum subarray
kadane algorithm java
kadanes
kadanes algorithm java
data structure algorithms kadanes algorithm
kadane's algorithm in c
kadane's algorithm java
kadanes algorithm explained
kadane's algorithm
kadane algorithm
kadanes algorithm
algorithm
kadane
kadane algorithm c++
kadane's
kadane algorithm java
algorithms
kadanes algorithm maximum sum subarray
kadanes algorithm to maximum sum subarray
kadane's algorithm maximum sum subarray
kadane's algorithm in c
maximum sum subarray kadane algorithm
kadane algorithm 2d
kadane algorithm dp
kadane algorithm complexity
kadane's algorithm to maximum sum subarray problem
kadane's algorithm
kadane algorithm
kadane's algo v.v.v.v.v imp
largest sum contiguous subarray
kadanes algorithm
maximum subarray
maximum subarray problem
maximum sum subarray
maximum subarray sum
anuj bhaiya
maximum subarray leetcode
kadane's algo
kadens algorithm
kadane’s algorithm
subarray
kadane
kadane algo
kadanes algo
maximum sub array
maximum product subarray
max subarray
kadane's algorithm in hindi
max subarray sum
find largest sum contiguous subarray
algorithm
maximum circular subarray sum
max sum subarray
kandane algorithm
leetcode 53
max sum contiguous subarray
subarray with given sum
max sub array
maximum subarray
dsa
kadane algorithm in hindi
split array largest sum
max product subarray
longest and subarray
subarray sum
dsa one
max circular subarray sum
maximum frequent subarray sum
continuous subarray sum
subarray sum equals k
algorithms in java
anuj bhaiya dsa
array algorithms
leetcode maximum subarray
maximum sum triplet
algorithms
greedy algorithm
anuj
array algorithm
find subsequence of length k with the largest sum
kadane's algorithm hindi
maximum sum rectangle
aditya verma dynamic programming
contiguous subarray
kadane's algorithm jenny
maximum beauty subarray
maximum sub array sum
maximum sum circular subarray
subset sum problem
two pointer
algorithm course
k-th largest sum contiguous subarray
longest subarray
max subarray problem
maximum frequent subarray sum codechef solution
maximum subarray sum cases
anuj bhaiya java
apna college
contiguous array
dsa course
find largest sum contiguous subarray [v. imp]
given an array arr[] of n integers. find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
kadens algo
longest and subarray codechef
maximize the sum hackerearth
maximum contiguous sub-array problem
partition array for maximum sum
algorithm in java
kadane's algorithm
kadane algorithm
kadane's algo v.v.v.v.v imp
largest sum contiguous subarray
maximum subarray
kadanes algorithm
maximum subarray problem
maximum sum subarray
maximum subarray leetcode
maximum subarray sum
anuj bhaiya
kadane's algo
kadens algorithm
kadane’s algorithm
subarray
kadane algo
kadane
kadanes algo
maximum sub array
max subarray
maximum product subarray
kadane's algorithm in hindi
max subarray sum
find largest sum contiguous subarray
algorithm
maximum circular subarray sum
53. maximum subarray
leetcode 53
max sum subarray
kandane algorithm
max sum contiguous subarray
subarray with given sum
max sub array
dsa
split array largest sum
kadane algorithm in hindi
subarray sum
max product subarray
longest and subarray
dsa one
leetcode maximum subarray
max circular subarray sum
maximum frequent subarray sum
continuous subarray sum
algorithms in java
greedy algorithm
subarray sum equals k
anuj bhaiya dsa
array algorithms

[@Krishna-le2vz]

Bhaiya aap hmare liye itni mehnat krte h to apkr liye like to bnta h
Love u bhaiya ♥♥

[@vishnuvardhanreddy9075]

Watched many videos but now finally I understood this algorithm clearly. Excellent explanation bro. Keep doing the work.

[@masqueradeee]

I was struggling for hours with this algorithm, Thanks for the detailed explanation.

[@anshulkumar1550]

Bhai sahab !!!! Kitne acche se samjhaya aapne. Maza aa gaya Anuj Bhaiya. Thank you.

[@ritiagrawal4051]

This is once of the best explanation i have heard about any DS algorithm. You not only explained the solution but explained how should we think. thanks a lot

[@mdyusufansari8897]

can you help me pleawse

[@SumitK-n8p]

​@@mdyusufansari8897 ladki se hi q help chiye

[@jaishreesaraswat3629]

I knew this algorithm but was struggling with an explanation ....really appreciable work !

[@world4376]

i too did you get placed ????

[@devyanshbansal8728]

Damnn right i was not able to understand the tutorial in my paid course

[@pranav288]

@@devyanshbansal8728 F

[@rbk.technology4747]

I guess the tweek is to make maxsum as -INF and not 0.
My point is if all elements are neg - then simply the task is now to return the max in neg arr.
Make this before hand.

[@shubhammazumdar8436]

Best explanation so far !! Have watched many videos to get clarity on this but your video turned out to be the best. !!

[@sabbiralshafi8684]

my watching lots of videos, I have to say that it is the best one. after watching for 2 minutes I understand the whole concept.

[@aksheshdoshi]

Very good explanation. I looked at other videos with way more views than this but this is the only way I understood it (that too in an intuitive way).

[@TaherAli-wb4ob]

This is the easiest explanation on kadane's Algorithm by far that i have seen on YT. Thank you for explaining the though process.

[@rohitk472]

for all negative values ---->
class Solution {
public:
int maxSubArray(vector& nums) {
int current = 0;
int max = -10000000000;
for(int i = 0; i < nums.size(); i++){
current = current + nums[i];
if(current > max){
max = current;
}
if(current < 0){
current = 0;
}
}
return max;
}
};

[@srinivassr5067]

dude u have literally written the same one that he explained.
You were trying to solve for one with all elements being -ve right?

[@monotonic_non_decreasing4618]

Bhaiya, sahi mai maja aa gaya, poora samaj aa gaya, ek baar mai, khud algo banayi maine aapke samjaane k baad, thodi mistake kardi thi, aapka code dekha phir correct kar li, thank you bhaiya, I wish you good health and great life ahead..

[@karanrai6772]

Bhaiya sach me pure youTube pr ap or hi ho jo achhe se explain krte ho love ❤ you dil se bhaiya

[@mohammadbilal1316]

Thank you anuj bhaiya aapne jo samjhaya kadane algo ko itne easiest way me wo koi aur nhi samjha paaya aap hamare guru ho programming ke again thank you 3000❤️

[@siddharthtripathy3964]

finally found a video which actually explains rationale behind each line of an algo.

[@sameerk047]

Superb explanation, I was breaking my head to understand the logic to get max sub array when all the element are negative.

[@aniketborkar9185]

Nice explanation!
For an array with negative values:
int max(int a, int b)
{
int temp = a>b?a:b;
return temp;
}
int maxSubArray(const int* A, int n1) {
int i,j,curr_sum=A[0],max_sum=A[0];
for(i=1;i

[@hemant64616]

if the question is this a = [1] .. why it is not working and showing error give me its solution it showing greater value 0 the actual answer is 1

[@ahmadfarazansari284]

Best explanation of kadane's algorithm so far.

[@202_b_ashishojha8]

If all the elements are even negative :
int current_sum = 0, max_sum =INT_MIN;
for(int i =0;i

[@Jarvis-cw5vu]

To the point solution bro!!

[@rajeevsankhla5028]

@@Jarvis-cw5vu max_sum=nums[0]; also works fine

[@sparshtaneja]

@@rajeevsankhla5028 only if array is sorted

[@kunalsoni3906]

if all the elements are negative then it should print the lowest negative integer and this code is not working.

[@vishalsinghpanwar2972]

@@rajeevsankhla5028 how did you get the intuition to use max_sum=nums[0] instead of max_sum = 0 like told in the video?

[@Rakshit_Jain]

I tried this algo from apna college also , no compe to this elaboration 🤝🏻

[@rohitrohra7553]

Anuj bhaiya , u earned a subscriber , for explaining this. Thanks for the explanation and thought process. You ar doing a wonderful job

[@vivekkr83]

By hearing the name I was thinking it would some complex algo. But you explained it very well, its very simple. Thank you

[@nancyagarwal8570]

Saw ur video day before yesterday, and yesterday I gave one written exam and same question comes, and I did in 2 mins.
Thankyou for such wonderful explaination. :)

[@ashutoshrai2717]

Is this question asked in your interview

[@mohdsahil226]

zabardast explaination. Didn't get this kind of explaination even on udemy! Heads off! Thank you!

[@sahilarora7186]

Bhaiya. Abhi urvi didi ka explanation dekha . Smjh ni aya.. fir search kra kaden's algo. Apka search ke top pe aya. 1 bar m smjh aa gya. Ye. 🙏Thanks a lot.

[@anjonroy7408]

So nicely explained . Appreciate your effort. Thanks a lot

[@raisanjeeb42]

Thank You bhaiya...I was struggling a lot in this algorithm..But This one video and all concepts clear

[@mohitnegi3641]

Thanks bro. made it simple and something I will never forget

[@sagarjoshi3481]

Thanks,
For the great explanation. I am struggling hours in this problem and got a very big solution, but your answer is short and easy to understand.

[@ayushthakur733]

Keep making such videos, your explanation is so brotherly islye acha smjh aata h

[@crazeeealgorithms3236]

Great Explanation , A big Thank You..., post more such videos.

[@aneezahayatshaikh3176]

Really very nicely explained and also in very easy manner to understand... thanku so much sir!!!

[@pawanchandrajoshi841]

this one works for negatives as well :)
int maxSubArray(vector& nums) {
int sum=nums[0], max_sum=nums[0];
for(int i=1; imax_sum)
{
max_sum=sum;
}
}
return max_sum;
}

[@yogeshsingh1621]

It worked thanks

[@swarnadipadhikary6809]

if you initialize max_sum=INT_MIN;

[@prathameshspai9878]

Put max_sum = INT_MIN

[@chinmaypisal7060]

@@swarnadipadhikary6809 why ? can you explain pls ??

[@abhijeet800]

@@chinmaypisal7060 jadu bro jadu. ;-)

[@rudro314]

Best dsa course ever on youtube

[@mohdzunaid9309]

@@sumanmalakarvlogs18 I can definitely say that!

[@rudro314]

@@sumanmalakarvlogs18 of course....apna college isn’t good at all

[@ray-lw7bf]

@@sumanmalakarvlogs18 1)apna college C++
Course aacha present kiya hai..bt utna depth me analysis nhi kiya code ko
2) dsa one me anuj bhaiya ne bhut systematic video banai hai...

[@shivangigupta8196]

i saw many videos but your explanation was great thanks alot

[@058__shivamverma7]

It can easily handle negative elelments also
class Solution{
long maxSubarraySum(int arr[], int n)
{
long sum=0;
long maxi=arr[0];
for(int i=0;imaxi){
maxi=sum;
}
if(sum

[@AllDimension]

Bhaiya maza agaya itna ache se mei kisise bhi nhi padha ye algorithm , ek baar mei pura dimag k andar.

[@abhishekarora437]

Very good course... Watching it since start.

[@anuraggulati2167]

cleared all the doubts thankyou anuj bhaiya..

[@balakrishnanr648]

Bhaiya, do more courses like this, as in-depth thought process is what most needed, then comes next thing that is - link multiple probs which applies almost same technique with variation.

[@hamidakbar42]

Thanks bruh..... I don't use to comment on videos. But this explanation forced me to do so. Bhai bahut hi simple samjhaya hai bhaiya ne. If anyone is struggling with this lect is for you

[@gitanjalikumari9262]

GREAT EXPLANATION..THANKS BHAIYA

[@Piyush-yq9iu]

Thank You for such an amazing lecture.

[@deveshsrivastava9121]

Thank you Anuj Bhaiya (SIR)
Keep up the good work.

[@yogeshdharya3857]

Thanx Dada.Theory se samajh nahi pa raha tha.Video explanation se clear hua .Love and support from Jabalpur

[@fenil861]

Simple and clear explanation. Thank you

[@govindam94]

Explanation is very good and easy to undestand. If every element is negative then it is very simple, just check which element is least negative.

[@Subash.IIT-Delhi]

If all elements are negative then just traverse the array and find the element which is having samallest magnitude that will be the answer

[@259_parthpatidar9]

yes bro it is simple like that

[@venkateshvenky2880]

Initialize maxsum as minus infinity...

[@rahulsaw8838]

Sum be will be equal to zero if all element are -ve and if sum equal to zero then maintain a variable for greatest element and scan while taking input

[@KrishnaGupta-xd6xu]

@@rahulsaw8838 So lengthy solution.

[@ravikishankumar332]

@@venkateshvenky2880 yes right bro. this will also work for all negative element.

[@AyushSingh-qr3go]

Thanks a lot bhaiya after struggling a lot I got right video and channel 🙏

[@Onesided.x]

Great explanation sir i didn't even saw a simple explanation like you. Although great 👍 sir

[@uk1523]

Initially maxSum with INT_MIN

[@mr.crazyunknown7094]

not really....blank array is a valid subarray.... so In case the max sum is negative ...you can just take a blank subarray....and thus max_sum will be non-negative (i.e. zero or positive)
Besides...starting with INT_MIN...and you face a negative number....you will run into overflow

[@ayushthakur733]

@@mr.crazyunknown7094 what if all the elements are negetive

[@mr.crazyunknown7094]

@@ayushthakur733 the proper output in that case should be an empty subarray.....so the sum will be zero..
There are variations in the question tho....sum question might ask you to find non-empty subarray

[@adityasinghrathore3935]

@@mr.crazyunknown7094 It depends. Leetcode expects subarray of length > 0

[@himanshusharma9239]

if all elemnts are negative then it will work

[@vibhutipatel2315]

Thank you so much bhaiya, you explained it very smoothly and nicely. Here we just need to make " maxSum = Integer.MIN_VALUE " (in java) for the correct output for all negative elements.!!

[@anshvashisht8519]

can u tell how does it work?

[@abhinavsaxena9846]

Thank you bhaiya you explained better than the teachers of apna cllg🥰🥰🥰🥰🥰

[@rohit45749]

After , seeing code the overall concept is clear at the end , thank you bhaiya

[@swapnilpatel9831]

Best explanation in whole CZcams.

[@subodhkumarbr]

Thanx a lot Bhaiji From Inner of Sole for providing this course
It might look crazy but I am a JEE Aspirant but still watch your DSA Course in my free time because i am very much enthusiast about the way of your teaching and know there student every crux of matter
Again to say THANK YOU VERY MUCH

[@garwitty]

get a life bruh

[@kritartha007]

Works for every cases:
int maxSubarraySum(int arr[], int n){

int currMax=0;
int Max=0;
for(int i=0;i

[@kritartha007]

Logic: If after adding arr[i] to current sum i.e.{ currSum+=arr[i]}, if current Sum is less than arr[i] or the added number, then this means left subarray sum is smaller than arr[i]. So , we update currSum=arr[i].
else, if current sum is not less than arr[i], then there is no issue.
Now, we have to check current sum with the maximum sum.
If current sum> maximum sum-----> update maximum sum to current sum.
after all the numbers are traversed , simply return the maximum sum

[@Anonymous-coder31]

Amazing easy to understand
Thanks bhaiya 😍😍😍

[@gauravanand_11]

You cleared my concept :)

[@manvibhardwaj725]

Thank you sir, the explanation is fantastic.

[@chandrabhachatterjee2472]

you explained this like crystal clear concept

[@vasudhatapriya6315]

Greatly Explained!

[@mrcharm767]

Bhaiyaa apki approach hamei badiya lagii please lage rehna aise lectures k sath hamara support apke sath h

[@somnathchakraborty1965]

Thank you bhaiya for explaining very simple way....

[@hrishikeshmhetre9163]

is vale number ka "yogdan" yahi tak tha . satya vachan bhaiya...

[@extremesatyaiitjeeair1980]

incase the array is all of negative elements and you want subarray of atleast 1 size then you have to add this code after Kadane's algo
if(maxsum==0)
{
maxsum=a[0];
for(int i=1;imaxsum) maxsum=a[i];
}

[@_HarshitSharma]

Jio bhaijaan ! Boht bdhiya explanation..!

[@AmanSingh-rz1rj]

Wow bhaiya really helpfull carry on bhaiya 😊

[@SAKSHIKUMARIP]

Clear explanation .tqqq sooo much bhaiya

[@Nandhubhai_bolthe.]

i very glad because i understand only in single vedio thankyou so much for this vedio

[@n-az563]

I struggled for this algorithm a lot even for O(N2) I could not get it.Thank you for your explanation

[@tushargarg3765]

Thank you for the nice explanation but,
Maxsum should be initialized to A[0] otherwise in the case of A=[-2] it will give 0 as output.

[@subhanjanbasu4642]

Underrated comment

[@kmohammedalthaf3535]

negative infinity is also fine I think

[@nawaz_haider]

@@kmohammedalthaf3535 yeah. but A[0] is more easy to understand

[@AnishKumar-fr4ye]

most underrated comment it should be pinned

[@rbk.technology4747]

Yah this willl then work for neg arrays too

[@surajbaranwal56.]

God bless you bhaiya, very well explained.

[@technocratsujal]

Kya behetreen Samjhaya hai Bhaiya Aapne Love You!

[@Yash_Parashar]

Best dsa course bhaiya inspiration 🙏🙏🙏

[@amankeshri3823]

Initialize MaxSum with very large -ve values (within range of integer) then it will pass all test cases

[@swagatpandak7325]

but will occupy more space than when you initialize it with max_sum=nums[0]; it will pass all cases and also occupy less space.

[@kanikamatta3503]

If we initialize max = arr[0] then this will work for negative cases also

[@rohitrohra7553]

Once i get a switch i ll give the highest thanks , as a token a appreciation.

[@varunyadav6560]

Great EXPLANATION 👏

[@rajattiwari6697]

Nice Explanation.I found one error .maxSum should be initialized by a[0] as for example if the first element is -1,then some test cases will be failed .And for all negative it will be replaced by INT_MIN

[@manusharma9089]

thankyou too!

[@jyotipandey3156]

U r the best... No animation content can ever beat u❤️❤️❤️❤️😘....loads of luv....it's quite help full ..a saashtaang dandwat pranaam to ur laymen type of explanation...plz complete this series as soon as possible ❤️❤️👍👍👍👍🙏

[@rajeshagarwal4137]

Direct attack on apna college; tauntbazi

[@harshittripathi3985]

@@rajeshagarwal4137 I came here to comment on apna college nautanki, nd suddenly I found ur comment 😂😂

[@faizanusmani2200]

Very easily explained. Zabardast Video.

[@krishanuchakraborty3500]

If all the elements are negative or otherwise, we can declare the maxSum like below:
int maxSum = Integer.MIN_VALUE;

[@bhavyagupta3565]

op i love you, bada pyara samjhaya!!!

[@himanshuchoudhary2514]

BEST VIDEO ON KADANE'S ALGO .... I SEEN MANY VIDEOS BUT THE WAY BHAIYA IS TEACHING IS SUPER AMAZING.....CLEARING THE WHOLE CONCEPT ....THANK YOU...............I SEEN IN MANY VIDEOS THEY JUST MEMORISE THE CONCEPT BUT IN THIS VIDEO I KNOW WHAT THE ALGO MEANS...AND THATS THE KEY ....🧠😊

[@nagpuri4390]

Why we have taken sum=0 when sum

[@himanshuchoudhary2514]

@@nagpuri4390 it because negative value will decrease the total sum of subarray..

[@user-ds4ym3hs4e]

Your explanation was everything 🙌 ❤

[@brijeshkumarverma1223]

correct ans for gfg que is:
long long maxSubarraySum(int arr[], int n){
// Your code here
long long cur_sum=0;
long long max_sum=INT_MIN;
for(int i=0;imax_sum){
max_sum= cur_sum;
}
if(cur_sum

[@ritikkhandelwal2358]

Anuj bhaiya.....bhot sahi bhot sahi😍😍

[@Lucifer-jl9vh]

Good explanation..Thank you Anna

[@animeshkumar_corporatevlogger]

maxSUm should be initialised with INT_MIN, great explanation bhaiya. Really helpfull.

[@TheMdaliazhar]

This is great and easiest explanation i have found. Thanks for sharing this for free. your explanations are in general better than many other popular youtubers in same category.
Suggestion: This code will fail in case `all the numbers are negative`. and to handle this edge case we just need to initialized top two variables with undefined value and use ternary operator during value assignment.

[@ebrahimali2689]

your explanation is just wow.

[@jayeshwaghmare2989]

if all elements are negative then max sum should be initialized to minus infinity or INT_MIN

[@dhruvpatel2039]

Better keep min_sum equal to the first element

[@shivamsinha5554]

bro both are same int min is the lowest value that can be stored in interger variable

[@joyboy1088]

@@shivamsinha5554 [-3, -1] take this array and try to find out the max sum using the approach taught. (ans is -1 but you will 0 since we are ignoring the negative numbers)

[@kmohammedalthaf3535]

yes exactly, it's a solution for any number...

[@pranay_gupta]

@@joyboy1088 simpy initialize with arr[0]

[@hardikverma5191]

thanks a lot bhaiya!!! very nicely explained : - )

[@ritiksaxena1984]

This will work for all the negative as well as positive nums
int ms,cs;
ms=cs=arr[0];
for(int i=1;i

[@P_S_PATIL]

no

[@Knowledgeduniya1432]

Beauifully explained bhaiya thanku

[@ABHISHEKKUMAR-bl5wy]

Great explaination sir !!!!!!!!

[@anshumanupadhyaycodes]

liked a video on YT after a long time!

[@MayankSharma-sf3hy]

So good would love to see more

[@himanshuthakur272]

Thanks bhaiya...you explained nicely..