bro in case of printing we must have keep track of only last index, think of it, bcz if after getting maxsum and startind and endind of subarray , if we further get the sum to be negative and then we put sum=0 and startindex to that index and think if we dont get any subarray that have sum greater than previous one, then we lost our startind and endind of main subarray ,then this will give wrong answer so correct solution for it will be keep only track of endind, so next time when we get higher sum then only change it. and after getting maxsum we can easily get our subarray by using last ind, by going on left side of ind and rightside of ind
Couple of years back, I had watched the best video on TH-cam(in terms of views) on Kadanes and still it was not very clear to me. And this video is so so better than the other video. Top level walkthrough. P.S: I am not comparing. Else I would have told which video was that which I watched earlier :)
#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....
yup it will not work if every element is negative so in the end max will be negative but we want 0 as answer so i did it myself (added that condition )after the for loop
Time Stamp 0:00 - Introduction to course 0:41 - Problem Statement 2:13 - Brute Force Solution 6:12 - Better Solution 7:40 - Optimal (Kadane's Algorithm) 13:18 - Code 15:29 - Time Complexity 15:40 - Follow up question 19:37 - Outro There's always something new to learn from striver's videos . Thank You bhai for posting videos without any long gap!!!.
Seriously, I really understood this 😮 The intuition is just common sense lol, If we add negative subarray sum to the next negative element it will decrease the value of our new subarray sum, even if we add negative subarray sum to our next positive element it will again decrease the value of our new subarray sum
The result will never be lesser than zero because one condition is "if(sum>max) max=sum" and initially sum=0 and max=LONG_MIN. hence, max will always be zero if all the values in the array are negative.
It is returning maxi variable so even if it is sum is negative and we make sum zero and then add a negative number to sum it will be lesser than the maxi variable
🎯 Key points for quick navigation: 00:43 *🧩 Introduction to the problem of finding the maximum subarray sum* - Definition of a subarray as a contiguous part of an array - Explanation of how to identify subarrays with maximum sum in an array 02:18 *🔄 Brute force approach to finding the maximum subarray sum* - Iterating through all possible subarrays to find the maximum sum - Detailed explanation of the nested loops to generate subarrays and calculate sum - Analysis of time and space complexity for the brute force approach 06:14 *👍 Improved approach to finding the maximum subarray sum* - Utilizing observations to optimize the brute force approach - Updating the sum incrementally without reiterating through each element - Analysis of the improved approach's time and space complexity 07:51 *🚀 Introduction to Kadane's Algorithm for the maximum subarray sum* - Description of the Kadane's Algorithm for finding the maximum subarray sum - Implementation steps of Kadane's Algorithm for optimizing the solution further - Understanding the logic behind dropping negative sums in Kadane's Algorithm 17:06 *📜 Modifying the Kadane's Algorithm to track and print the subarray with maximum sum* - Introduction of additional variables to track the start and end of the subarray - Explanation of how to modify the Kadane's Algorithm code to print the subarray with maximum sum - Discussion on maintaining the time and space complexity while adding printing functionality Made with HARPA AI
Love your explanation of progression of solutions and code walk through. Please keep making precise and amazing content like this. It really helps to stay motivated with solving problems because when I'm stuck, the logic in your vids is explained very clearly. Thanks a lot!!
If you're doing on leetcode where negeative also consider where code follows, int maxSubArray(vector& nums) { int cs =0,ms=nums[0]; for(int i=0; i< nums.size(); i++){ cs += nums[i]; ms = max(ms,cs); if(cs < 0) cs = 0; } return ms; }
1. is the carryforward and sliding window technique is both are same? 2. can you please tell me the difference between carryforward and sliding window technique? it will be really helpful if you explain me sir.
2 pointer approach to solve the problem ,may give tle where 0(n) is expected: class Solution { public: int sums(int prev,int curr,vector nums) { int s=0; for(int i=prev;i
#include long long maxSubarraySum(int arr[], int n) { //Kadan's Alogrithm ->move and keep adding and if less then 0 and then neglect long long sum=0; long long maxi=LONG_MIN; for(int i=0;imaxi){ maxi=sum; } if(sum
kadane's algorithm c++ code: there was error in editing so i wrote the code this might help beginners like me :) #include using namespace std; int main() { int n = 8; int arr[n] = {-2, -3, 4, -1, -2, 1, 5, -3}; long long sum = 0, maxi = LONG_MIN; int start = 0, end = 0; for (int i = 0; i < 8; i++) { if (sum == 0) { start = i; } sum += arr[i]; if (sum > maxi) { maxi = sum; end = i; } if (sum < 0) { sum = 0; } } for (int i = start; i
in the brute approach is 3 for loops needed? #include using namespace std; // #include int maxSumSubarray_brute(vectorarray){ int prevsum =0; int maxsum = INT_MIN; for(int i=0;i
sir i know its weird to ask but sir i want to ask you that we just learned the method by watching lectures cause i don't know about kadane's algorithm and more such type of methods, or we have to practice it without watching the video .pls reply what is better to do.
For those solving this in 2024 , if you try to submit this on leetcode this will fail on the test case [-1] since obviously our array has only one neg element ,it shall return -1 but in our case it will return 0..., You can refer the following code to solve it instead : int maxi = nums[0]; // Initialize maxi to the first element int sum = nums[0]; // Initialize sum to the first element int n = nums.size();
for (int i = 1; i < n; i++) { sum = max(nums[i], sum + nums[i]); maxi = max(maxi, sum); }
Hi , I am unclear why O(n^3) solution is needed even in brute force solution when it can be done in O(n^2) solution , sum can be found out in the 2nd loop itself. If you read the post please clear the doubt. thanks
Yes it can be done in n², declare sum variable after i loop, before j loop, while adding elmts in sum in the j loop, everytime keep updating max, once j loop finishes, sum will be back to zero
Thank you very much bhaiya for these. In upcoming videos please add general approach for techniques like sliding window, two pointers etc techniques as the way you give for recursion and dp etc. Thank you once again bhaiya
sir in the follow up question if we take the array as {-1,-2,-3,-4} your solution will give answer as (3,3) whereas the correct answer should have been (0,0)
Can it optimise further more ? Follow up question: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Please watch our new video on the same topic: th-cam.com/video/AHZpyENo7k4/w-d-xo.html
It's recursion!!!
lol i kept on clicking the link and its the same link (not recursion but yeah a loop)
Delete the link
13:56 "Do not carry any negatives into your future" - Striver
Even thought the context was different, it can be applied in our real life❤
TRUE
Nice Humor
Let's march ahead, and create an unmatchable DSA course! ❤
Use the problem links in the description.
bro in case of printing we must have keep track of only last index, think of it,
bcz if after getting maxsum and startind and endind of subarray , if we further get the sum to be negative and then we put sum=0 and startindex to that index and think if we dont get any subarray that have sum greater than previous one, then we lost our startind and endind of main subarray ,then this will give wrong answer
so correct solution for it will be keep only track of endind, so next time when we get higher sum then only change it. and after getting maxsum we can easily get our subarray by using last ind, by going on left side of ind and rightside of ind
hey is it same for longest subarray sum
Always ready for Dsa ✅
Haan Bhai
jhuk fir
weird how this explanation of kadans algo is so simple compared to other yt videos. short algo short code. superb
Couple of years back, I had watched the best video on TH-cam(in terms of views) on Kadanes and still it was not very clear to me. And this video is so so better than the other video. Top level walkthrough.
P.S: I am not comparing. Else I would have told which video was that which I watched earlier :)
#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....
at 15:22 you have to add this code in for loop . if(maxi
yup it will not work if every element is negative so in the end max will be negative but we want 0 as answer so i did it myself (added that condition )after the for loop
I did it by myself ..😅i found the logic after 10min I started..it feels so good . I don't know this problem is hard or not
Time Stamp
0:00 - Introduction to course
0:41 - Problem Statement
2:13 - Brute Force Solution
6:12 - Better Solution
7:40 - Optimal (Kadane's Algorithm)
13:18 - Code
15:29 - Time Complexity
15:40 - Follow up question
19:37 - Outro
There's always something new to learn from striver's videos . Thank You bhai for posting videos without any long gap!!!.
BEST Kadane's algo video on the internet!
The build up to the optimal and follow up question is fire.
Complete concept clarity in 20 mins. Amazing ✅✅✅✅
Printing the subarrays part is something i learn this time tysm understood:)
"Understood " superb intuition of algorithm !! awsome explanation i request everyone whoever watching strivers vedeos do like and comment!!!
Kadame's Algorithm is now clear. Thankyou Striver ❤
From brute(TC -> O(N^3), SC -> O(1)) to better(TC -> O(N^2), SC -> O(1)) to Optimal(TC -> O(N), SC -> O(1))
in love with kadane algorithm...all thanks to you bhaiya
Bro its 2pm night in India, You are doing great Job, consistency 💥
He is in warsaw, which means he uploaded the video between 9:30-10 pm in his time
Yes I could not do it during the morning today. Came back from office and recorded, edited and uploaded 😄
Am hai🤭🤭🤭
@@takeUforward Thats why your content is the best
Nothing can describe how thankful we're to you for such amazing content.. . God Bless you Striver.. Hope you achieve everything you want ❤️❤️
Great teaching by great teacher ❤
15:05 editing mistake 🫡 but no worries
shit yes, thankfully not a big one
@@takeUforward please make a video on long pressed name
@@takeUforward which tool you are using for white boarding?
Seriously, I really understood this 😮
The intuition is just common sense lol,
If we add negative subarray sum to the next negative element it will decrease the value of our new subarray sum, even if we add negative subarray sum to our next positive element it will again decrease the value of our new subarray sum
i saw many videos but not able to understad.... this video gave me complete understading..Thanks bro
Really amazed by the effort you put into making us understand. Thank you, Striver!
12:28
very nice explaination. Very helpful walk through that cleared my confusions
The result will never be lesser than zero because one condition is "if(sum>max) max=sum" and initially sum=0 and max=LONG_MIN. hence, max will always be zero if all the values in the array are negative.
It is returning maxi variable so even if it is sum is negative and we make sum zero and then add a negative number to sum it will be lesser than the maxi variable
no it will return the biggest -ve number if there are all -ve in array
if all elements are negative it returning the biggest negative value because even we keep sum=0 when sum if(maxi
BEST TEACHERRRR EVERR!!!!!!!!!!
13:57
Don't carry any negatives into future 😇
Easiest explaination ever👌👌 thanks bhaiya...!!
Understood....Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
🎯 Key points for quick navigation:
00:43 *🧩 Introduction to the problem of finding the maximum subarray sum*
- Definition of a subarray as a contiguous part of an array
- Explanation of how to identify subarrays with maximum sum in an array
02:18 *🔄 Brute force approach to finding the maximum subarray sum*
- Iterating through all possible subarrays to find the maximum sum
- Detailed explanation of the nested loops to generate subarrays and calculate sum
- Analysis of time and space complexity for the brute force approach
06:14 *👍 Improved approach to finding the maximum subarray sum*
- Utilizing observations to optimize the brute force approach
- Updating the sum incrementally without reiterating through each element
- Analysis of the improved approach's time and space complexity
07:51 *🚀 Introduction to Kadane's Algorithm for the maximum subarray sum*
- Description of the Kadane's Algorithm for finding the maximum subarray sum
- Implementation steps of Kadane's Algorithm for optimizing the solution further
- Understanding the logic behind dropping negative sums in Kadane's Algorithm
17:06 *📜 Modifying the Kadane's Algorithm to track and print the subarray with maximum sum*
- Introduction of additional variables to track the start and end of the subarray
- Explanation of how to modify the Kadane's Algorithm code to print the subarray with maximum sum
- Discussion on maintaining the time and space complexity while adding printing functionality
Made with HARPA AI
SDE Sheet Day 1 Problem 1 Done!
Crystal Clear Understanding !
i was very keen about learning DSA and your sheet and your explanation has boosted this thank you strive bhaiya
Love your explanation of progression of solutions and code walk through. Please keep making precise and amazing content like this. It really helps to stay motivated with solving problems because when I'm stuck, the logic in your vids is explained very clearly. Thanks a lot!!
Understood,Thank striver for this amazing video.
If you're doing on leetcode where negeative also consider where code follows,
int maxSubArray(vector& nums) {
int cs =0,ms=nums[0];
for(int i=0; i< nums.size(); i++){
cs += nums[i];
ms = max(ms,cs);
if(cs < 0)
cs = 0;
}
return ms;
}
Thank You so much for made this crystal clear understanding about this problem.
bro i really love your explanation ;how ever i explane doudtes to my frnds you explaining in same manner ❤
Very detailed explanation, it is language agnostic as well, thanks for the video
class Solution {
public:
int maxSubArray(vector& nums) {
int maxi=nums[0];
int sum=nums[0];
for(int i=1;i
Understood! Super excellent explanation as always, thank you very very much for your effort!!
Bro really you have good knowledge of DSA...
Living in this era where striver exists is like living in era where Ronaldo and messi are alive together. I can't thank enough!
Im new to programming and this was very helpful ~
Thank you for this video, great explanation! I will need it for my exam in an hour haha!
Great explanation 🎉
1. is the carryforward and sliding window technique is both are same? 2. can you please tell me the difference between carryforward and sliding window technique? it will be really helpful if you explain me sir.
Nice man good teaching EXELLENT
understood you are the best teacher. 🙌
2 pointer approach to solve the problem ,may give tle where 0(n) is expected:
class Solution {
public:
int sums(int prev,int curr,vector nums)
{
int s=0;
for(int i=prev;i
Thank you 🙏
Understood. Thanks Striverr!!1
done and dusted ! hats off to striver ..
Understood. Thanks a lot. Please upload more videos Bhaiyaaa.
#include
long long maxSubarraySum(int arr[], int n)
{
//Kadan's Alogrithm ->move and keep adding and if less then 0 and then neglect
long long sum=0;
long long maxi=LONG_MIN;
for(int i=0;imaxi){
maxi=sum;
}
if(sum
Understood, Amazing Lecture Sir!
Superb bro, exceptional 🎉🎉🎉
Super explanation with so much love 😃
you are doing great job striver ❤.. .
Understood!.Thank you.
Thanks for this, super helpful!
excellent explanation thanku so much
your course is too good
Tired of commenting AMAZING bhaiya ;) !! You're tooooo good :)
kadane's algorithm c++ code: there was error in editing so i wrote the code this might help beginners like me :)
#include
using namespace std;
int main()
{
int n = 8;
int arr[n] = {-2, -3, 4, -1, -2, 1, 5, -3};
long long sum = 0, maxi = LONG_MIN;
int start = 0, end = 0;
for (int i = 0; i < 8; i++)
{
if (sum == 0)
{
start = i;
}
sum += arr[i];
if (sum > maxi)
{
maxi = sum;
end = i;
}
if (sum < 0)
{
sum = 0;
}
}
for (int i = start; i
Thanku u
@@vaishalirawat2447 welcome.
Your way of explanation is really outstanding🔥🔥🙌thanks lot and more!!!!
Amazing!! Keep going bro⚡
perfect explaination.
Thank you bade bhaiya
in the brute approach is 3 for loops needed?
#include
using namespace std;
// #include
int maxSumSubarray_brute(vectorarray){
int prevsum =0;
int maxsum = INT_MIN;
for(int i=0;i
Thanks for explanation
8:20 "Do not worry" ✨
great concepts , understood everything
Understood ❤bhaiya❤❤
sir i know its weird to ask but sir i want to ask you that we just learned the method by watching lectures cause i don't know about kadane's algorithm and more such type of methods, or we have to practice it without watching the video .pls reply what is better to do.
Absolutely Amazing ✌️🔥
Best explanation everr
In interview can we give direct optimal solutions only ? Please tell anyone here
Nice explanation bhaiya
Understood striver! 🔥👍
Thank you striver your videos are helping alot
14:00 rule of life and rule for Kadane
Completely Understood!
Thanks brother Best Explanation😊
For those solving this in 2024 , if you try to submit this on leetcode this will fail on the test case [-1] since obviously our array has only one neg element ,it shall return -1 but in our case it will return 0..., You can refer the following code to solve it instead :
int maxi = nums[0]; // Initialize maxi to the first element
int sum = nums[0]; // Initialize sum to the first element
int n = nums.size();
for (int i = 1; i < n; i++) {
sum = max(nums[i], sum + nums[i]);
maxi = max(maxi, sum);
}
return maxi;
}
I know it should not work but idk why its working on lc?😅
I added the test case -1 from my side then also its working but it should return 0 LOL.
Hi ,
I am unclear why O(n^3) solution is needed even in brute force solution when it can be done in O(n^2) solution , sum can be found out in the 2nd loop itself.
If you read the post please clear the doubt.
thanks
Yes it can be done in n², declare sum variable after i loop, before j loop, while adding elmts in sum in the j loop, everytime keep updating max, once j loop finishes, sum will be back to zero
NICE SUPER EXCELLENT MOTIVATED
Thank you very much bhaiya for these.
In upcoming videos please add general approach for techniques like sliding window, two pointers etc techniques as the way you give for recursion and dp etc.
Thank you once again bhaiya
Understood bhaiya!
Striver is Love yr❤
Understood.. thank you so much bro
Understood. Thanks a ton 😇
sir in the follow up question if we take the array as {-1,-2,-3,-4} your solution will give answer as (3,3) whereas the correct answer should have been (0,0)
Can it optimise further more ?
Follow up question:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Man copy pasted the Follow Up of Leetcode on this question.
understood ,thnx for the video ❤❤❤❤❤❤
understood
// first time bro
nums = [-1, -2, -3, -4]
According to your solution, the start will be 3 in this case but the correct answer should be 0
understood 😇
Can't wait for binary search series