Maximum Subarray Sum | Leetcode | Kadane's Algorithm | Brute-Better-Optimal | CPP/Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

.
People thinking this does not works for negative numbers, have a closer look what maxi is initially initialised to.
.

[sasmalpayal]

I haven't seen people explaining any problem in the brute force approach as well as in an optimal solution. Thank you so much for your good work.

[tanyacharanpahadi]

since the last four days. your videos are the first thing i watch in the morning. Great job brother.

[Ramya]

2 yrs before i just reject his vedios because of some careless mistake of mine.i didn't have patience in that time. I was join for classes for DSA. but no uses. Now im here again for day and night with dsa vedios from striver channel.

Thank you man😇❤

[shobitjain]

In the O(N^2) approach, j has to be initialized with i, not 0 at the beginning of the loop.

[sourin.majumdar]

Never did Kadane's algorithm before but the way you explained, I wrote the correct code all by myself directly at one go!

[yashnarkhedkar]

📍To return subarray as well alongside maximum sum of subarray using kadane's algorithm
👇👇👇👇👇👇
void maxSubArray(vector<int>&nums, int n){
int maxi = 0, current_max = 0, start_index = 0, end_index = 0, j = 0;

for(int i=0;i<n;i++){
current_max += nums[i];

if (current_max > maxi){
maxi = current_max;
start_index = j;
end_index = i;
}
if (current_max < 0){
current_max = 0;
j = i + 1;
}
}
}

[ddarrsh]

this is the only video on web, that clearly clearly explains the O(N) Solution to this problem, thank you!

[AyushKumar-tpfb]

A big help for all the students as well as dsa learners . Thank you bro <3

[RajanayakiScse]

Never seen a great video explaining this algorithm, this much simple :) Thanks a ton, bhaiya. the kudos to you :)

[ShivamSingh-rjjd]

THIS IS THE BEST EXPLANATION OF KADANE'S ALGORITHM, CHANGE MY MIND ;-)). Great job brother!

[itzmartin]

Kudos for your dedication and crisp explaination!

[om__]

Great bro. Liked it.
I am a professional with 2 yrs of experience, and waiting for the new job from 5 months, and I am trying to prepare for faang, so that I can give intervoews next year. I am following this videos along with your faang video.
And the main thing that I like is, not everyone can give all the time due to all personal work, everyone doesn't have same life, some have to do home stuff and all, but you taking out your time for these videos. Great bro. I can't give 4 hrs a day also for ds but hope some product based company recruit me someday.
Thanks broooo for all your hard work.

[chaitanyamalegaonkar]

I think 'j' should start with 'i' instead of 0 for the bruteforce....the above bruteforce won't give the right answer if all the array elements are negative for ex.[-1, -2].but great video man!!

[MrChetan]

I like the way you take us from brute force to optimal step wise

[siddhanth]

For those asking about what if all negative numbers were in array, it'll still work:

Assume [-2, -1]

First pass: maxi set to -2
Sum = 0 + -2 = -2
Is Sum > maxi? No, so no update
Is Sum < 0? Yes, so no point carrying forward that sum, we just make it 0, so sum = 0

Second pass: maxi is currently -2
Sum = 0 + -1 = -1
Is Sum > maxi? Yes, update maxi = sum = -1
Is Sum < 0? Yes, so no point carrying forward this, update sum to 0

End, maxi = -1

[aadeshsharma]

ye bnda ninjas blocks gfg ka dhndha bnd krwadega, thnx bro for these helping videos

[samruddhipatil]

4:08, If the array contains only negative elements, then?

[KarthikNandam-xsqn]

int maxSubArray(vector<int>& nums) {
int m = nums[0];
int sum = 0;
for (auto a : nums) {
sum += a;
m = max(m, sum);
if (sum < 0) sum = 0;
}
return m;
}
beats 98% 🕺✅

[shivamarora]

Bro You are doing great for those who are not able to purchase costly DSA courses of CN and CB. KEEP IT UP.