Please watch the new video which covers it in more depth, and also prints it: ua-cam.com/video/AHZpyENo7k4/v-deo.html . People thinking this does not works for negative numbers, have a closer look what maxi is initially initialised to. . If you appreciate the channel's work, you can join the family: ua-cam.com/channels/JskGeByzRRSvmOyZOz61ig.htmljoin
Hello Bhaiya . Whenever I am trying to solve a question on codechef or geeksforgeeks , I am unable to solve the question , I did a lot of practice , I did understood the code and also I am choosing the right algo , but unable to solve . Can you please help ? I am using Java .
@@ritiksolanki6267 I have got multiple offers from TCS, Infosys, Wipro, Cognizant, Accenture. Without your guidance and motivation Ritik Sir. I am not able to get all this offers. Whole Acropolis is proud of you for having such a coder like you. #proud_acropolian
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😇❤
@@aayushranjan5572 O(n^2) approach will also work : class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; if (nums.length == 1) { max = nums[0]; } for (int i = 0; i
@@haripriyakulkarni3404 With i = 0, j will go from 0 to len With i = 1, j will go from 1 to len With i = 2, j will go from 2 to len .. With i = len - 1, j will capture len - 1 so, it taking sum of all subarrays and if it finds out max in between it will update. If you give me a test case where it will not work that would be great to understand where it is failing.
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
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!!
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.
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India..
int maxSubArray(vector& 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% 🕺✅
Is this brute force solution is applicable for all these problems----> Kadane's Algo,Largest Subarray with sum 0, Subarray with sum 0, Subarray with given sum?????
Thank you adding code at last, this help us, if we find any problem during our own implementation, thank you brother Make explanation video for all SDE sheet questions
We need to arrange the code a little bit more What if all the elements turn out to be -ve, and everytime sum will be improved to 0 and hence the maxi also... Thanks dada for your valuable time and suggestions and that are lot for us...thank u...
For the question where we had to return sub array with maximum sum.... I thought of using map to put that vector carrying subarray to that maxi variable mpp[maxi] = vector; then returning mpp[maxi];
there is a little error as our code assumes that the given array must have a non negative sum for a sub sequence . In the end we should filter out the output by checking weather it doesn't return a max sum as negative ................. add these at the end if(maxi "greater than" 0) return maxi; else return 0;
I noticed how many videos explain the process by saying temporaryMax = max(temporaryMax+arr[i], arr[i]). At first I was a little confused between what striver explained and all the other guys but when I think about it, max(temporaryMax+arr[i], arr[i]) == arr[i] if and only if temporaryMax < 0 because if temporaryMax carries a negative value, there is no point adding it. So striver is basically touching on the same thing.
Can anybody tell me the modification in this approach if all the elements are negative? Should we first check if all elements are positive or negative and then proceed accordingly?
Please watch the new video which covers it in more depth, and also prints it: ua-cam.com/video/AHZpyENo7k4/v-deo.html
.
People thinking this does not works for negative numbers, have a closer look what maxi is initially initialised to.
.
If you appreciate the channel's work, you can join the family: ua-cam.com/channels/JskGeByzRRSvmOyZOz61ig.htmljoin
Hello Bhaiya .
Whenever I am trying to solve a question on codechef or geeksforgeeks , I am unable to solve the question , I did a lot of practice , I did understood the code and also I am choosing the right algo , but unable to solve . Can you please help ? I am using Java .
Understood bro! 💯
Hey striver
Does anyone knows about Exposys Data labs internship
Is it recommended to take it?
They are asking for a registration fees.
Understood🔥
What if all the integers are negative??
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.
since the last four days. your videos are the first thing i watch in the morning. Great job brother.
Awesome! Thank you!
Same here😀.....your explanation is amazing 👍👍
@@ritiksolanki6267 Congratulations Ritik for Nagarro!!😇 Whole Acropolis is proud of you!🙌🙌
@@ritiksolanki6267 I have got multiple offers from TCS, Infosys, Wipro, Cognizant, Accenture. Without your guidance and motivation Ritik Sir. I am not able to get all this offers. Whole Acropolis is proud of you for having such a coder like you.
#proud_acropolian
@@coffeebeans9238 bro , how much you completed this sde sheet ??
Never did Kadane's algorithm before but the way you explained, I wrote the correct code all by myself directly at one go!
🥳
can relate
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😇❤
only if striver also made videos on spoken english
@@nova9157 lolllllllllll
In the O(N^2) approach, j has to be initialized with i, not 0 at the beginning of the loop.
but why pls explain
@@aayushranjan5572 O(n^2) approach will also work :
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
if (nums.length == 1) {
max = nums[0];
}
for (int i = 0; i
@@aayushranjan5572 initiallizing j with 0 doesn't make any sense since for n times (for i 0 to n-1)we will travelling the whole arrya(j= 0 to n-1)
@@RituSharma-zp7xs how will this cover all the subarrays?
@@haripriyakulkarni3404
With i = 0, j will go from 0 to len
With i = 1, j will go from 1 to len
With i = 2, j will go from 2 to len
..
With i = len - 1, j will capture len - 1
so, it taking sum of all subarrays and if it finds out max in between it will update. If you give me a test case where it will not work that would be great to understand where it is failing.
Never seen a great video explaining this algorithm , this much simple :) Thanks a ton , bhaiya. Alllllll the kudos to you :)
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
A big help for all the students as well as dsa learners . Thank you bro
Kudos for your dedication and crisp explaination!
this is the only video on web, that clearly clearly explains the O(N) Solution to this problem , thank you!
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
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
what about [-2,1] please explain that as well
📍To return subarray as well alongside maximum sum of subarray using kadane's algorithm
👇👇👇👇👇👇
void maxSubArray(vector&nums, int n){
int maxi = 0, current_max = 0, start_index = 0, end_index = 0, j = 0;
for(int i=0;i maxi){
maxi = current_max;
start_index = j;
end_index = i;
}
if (current_max < 0){
current_max = 0;
j = i + 1;
}
}
}
Brute force will only run 2 loops:
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum = 0;
for(int i=0;i
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!!
I like the way you take us from brute force to optimal step wise
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.
THIS IS THE BEST EXPLANATION OF KADANE'S ALGORITHM, CHANGE MY MIND ;-)). Great job brother!
ye bnda ninjas blocks gfg ka dhndha bnd krwadega , thnx bro for these helping videos
he is the only one helps me a lot ,i got so addicted to his vedio i am only doing problems he gave explanation .
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India..
bhai ye sab bakchodi likhna band kardo , aur padhai kar le thoda
u r a genius man ! aap brute se optimal tak le jaate ho, ye aapki bahot achchi habit hai.
i am final year student your video really helps me to understand the logics
The way you explain, makes everything easy ❤❤
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
maximum element should be initialized with Integer.MIN_VALUE if negative also considered
int maxSubArray(vector& 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% 🕺✅
Thank you bhai, love your method of taking us from the brute force to the most optimal approach.
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
Thank u striever..❤️
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
@@imshivendra just an alternative for (int i=0; i
@@pranav288 Thanks
The best teacher a CS student can ever have💕💕
Thanks bro. Your explanation is far better than gfg's own explaination video.
Here for loop for Brute force solution will be--->
for(int i=0; i
Is this brute force solution is applicable for all these problems---->
Kadane's Algo,Largest Subarray with sum 0, Subarray with sum 0, Subarray with given sum?????
best explanation. i have checked other videos but it was quite confusing
You are a very good explainer.
Thanks.
Glad it was helpful!
Brute force approach for this problem can be done in O(n^2) time
I am a beginner in cp and your videos are really helpful and informative. Thanks a lot, :))).Pls do make a lot of videos
Here is the correction in the code,if all elements are negative then it returns negative number,so if(maxi
Thank you adding code at last, this help us, if we find any problem during our own implementation, thank you brother
Make explanation video for all SDE sheet questions
Where I can find that sde sheet ?
@@random.__.. check the description box
superb explanation brooooooo , without seeing code, written logic
We need to arrange the code a little bit more
What if all the elements turn out to be -ve, and everytime sum will be improved to 0 and hence the maxi also...
Thanks dada for your valuable time and suggestions and that are lot for us...thank u...
Read the comments, already answered!
understood all (1-4) the problem
to deal with cases like [-1,-2]; max = maximum of value in array
Check pinned comment
Bro You are doing great for those who are not able to purchase costly DSA courses of CN and CB. KEEP IT UP.
Just addicted to your videos It's Raining outside and here raj said "i hope you doing extremely well" 😊😊
You have explained this algorithm so lucidly. Thank you! :)
For the question where we had to return sub array with maximum sum.... I thought of using map to put that vector carrying subarray to that maxi variable
mpp[maxi] = vector;
then returning mpp[maxi];
there is a little error as our code assumes that the given array must have a non negative sum for a sub sequence . In the end we should filter out the output by checking weather it doesn't return a max sum as negative .................
add these at the end
if(maxi "greater than" 0) return maxi;
else return 0;
thanks for the edge case
My Day Starts with your video , learning something new each day...
Thankyou brother..!
Understood. Thank you for explanation.
got this sir after a long research thankyou.
you are doing great job man this list is very good to cover almost every concept.
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
thanks for your efforts bro. understood clearly
I noticed how many videos explain the process by saying temporaryMax = max(temporaryMax+arr[i], arr[i]). At first I was a little confused between what striver
explained and all the other guys but when I think about it, max(temporaryMax+arr[i], arr[i]) == arr[i] if and only if temporaryMax < 0 because if temporaryMax carries a negative value, there is no point adding it. So striver is basically touching on the same thing.
UNDERSTOOD... !
Thanks striver for the video... :)
Thank You so much Striver...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
suppose [-2] input liye then expected output -2 aana chahiye but 0 aa rha jo ki galat h
2:59 For middle optimal we can also do by sorting and sum of all positive numbers or last number.
If you sort it wont be subarray anymore!
class Solution {
public int maxSubArray(int[] nums) {
int maxSum= nums[0];
int currentSum= maxSum;
for(int i=1; i
Best video on Kadane's Algo. Keep up the good work. Shakespeare's will keep criticising!
excellent brooo....nice explanatation
watch the new video..
This series is as awesome as it gets!
Great explanation, thank you.
Thankyou understood 🙂🙂💚💚
Best explanation ever...kudos ✨
Thanks again striver bhai ..thora time baad krne baitha bhul gya tha thora ..dobara se dekha phir ek naya chiz smzh aaya isi mein ❤❤👌
Very Well Explained 👍👍
Thank you, clear enough.
Very useful video. Crisp but effective
Can anybody tell me the modification in this approach if all the elements are negative? Should we first check if all elements are positive or negative and then proceed accordingly?
So we need to add extra if condition
//C Program(Applicable for both positive and negative numbers)
#include
int main()
{
int a[50],i,n;
int maxsum,cursum=0;
scanf("%d",&n);
for(i=0;i
Thank u bhaiya great 👏👏👏
thank you..this is helpful in clearing DSA basics
Great explanation mr
int maxSubArray(vector &arr) {
int current_max = arr[0], max_so_far = arr[0];
for (auto it : arr) {
current_max = max(current_max + it, it);
max_so_far = max(max_so_far, current_max);
}
return max_so_far;
}
Bro .. please keep uploading .. we are loving your videos..
excellent explaination thankyou
very well explained
thanku bhai It was easy to understand
you are great
very very very very well explained !! thankyou
Glad it was helpful!
@@takeUforward please complete one by one total 180 questions....
Best solution ever
Understood! So amazing explanation as always, thank you very much!
Awesome video Stiver, thanks
We all learning something new that all becoz of your video's
what if they want indices in which maximum sum is occurring?
Bhaiya pls prepare a java Sol along with cpp it will be very helpful ...by the way grt work.😇😇😇😇😇
Savi, can you please see the entire video? Java solution is there :)
@@takeUforward sir I am really sorry actually vid suddenly stopped (due to buffer I guess ) it was over ...my bad😔😔😔
Best explanation brother.......
very helpful bhaiya , great
understood..thank you bro
very good explanation
Your make coding Fun bro! Thanks for the simplicity
Thanks for your clear explanation 🙏🏻👌🏻.
Great.. What if we want to return the subarray too?
Put some if else.. will update the code in link soon
Really worth it for quick learning
Thank you so much sir. Completely understood.
1D DP is also a good solution
how should i remember all this algorithms which ur telling in every video like how buddy? should i note it down and revise after few days?
Thank you
Sirji great videos very helpful plz continue to upload some more 🔥🔥
Bhaiya what is written inside for loop(auto:it) I'm unable to understand
@@imshivendra auto takes the datatype whichever it is there over, and it itereates the whole loop
Awesome explanation bhiya 😊😊❤️
some time i forget to like but that doesn't mean you are not best you are best and best does not depend of count of likes
@takeUforward the solution does not cover the case when all elements are negative, it will return 0 instead of the smallest element.