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
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!!!.
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
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); }
LeetCode JAVA Solution: class Solution { public int maxSubArray(int[] nums) { int max= Integer. MIN_VALUE; int sum=0; int c=Integer.MIN_VALUE; for(int i=0;imax) max=sum; } if(max==0) max=c; return max; } }
i have a question , if in interview we do this question like brute force then optimal , do i need to mention the algo used , won't the interviewer think why i started with brute when i knew this algo need to be used?
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 :)
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.
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.
#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....
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)
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
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
weird how this explanation of kadans algo is so simple compared to other yt videos. short algo short code. superb
Nothing can describe how thankful we're to you for such amazing content.. . God Bless you Striver.. Hope you achieve everything you want ❤️❤️
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!!!.
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
Complete concept clarity in 20 mins. Amazing ✅✅✅✅
Understood! Super excellent explanation as always, thank you very very much for your effort!!
SDE Sheet Day 1 Problem 1 Done!
Thank You so much for made this crystal clear understanding about this problem.
Easiest explaination ever👌👌 thanks bhaiya...!!
Your way of explanation is really outstanding🔥🔥🙌thanks lot and more!!!!
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?
Superb bro, exceptional 🎉🎉🎉
Thanks a Lot
your course is too good
Absolutely Amazing ✌️🔥
Understood,Thank striver for this amazing video.
Understood ❤
super understood
best video
Tired of commenting AMAZING bhaiya ;) !! You're tooooo good :)
Understood!
understood bhaiya
great concepts , understood everything
Understood striver! 🔥👍
understood
Understood bro. Thank you
Completely Understood!
understood bhiaaaa!!!!
Understoood
You the goat
UNDERSTOOD !!
Can't wait for binary search series
Thank you so much for the video
amazing video sir
UNDERSTOOD SIR🙇♂❤🙏
Understood
Understood ❤bhaiya❤❤
All videos are very helpful
14:00 rule of life and rule for Kadane
understood !!
understood ,thnx for the video ❤❤❤❤❤❤
Incredible 🎉
Understood thanks 🙏
Thanks so much striver
UNDERSTOOD SIR
Array Lec2(medium) Q.5 solution :----------------------------------------------------------------------------------------------------------
class Solution {
public static long pairWithMaxSum(long arr[], long N)
{
long maxSum = Long.MIN_VALUE;
for (int i = 0; i < N - 1; i++) {
long currentSum = arr[i] + arr[i + 1];
if (currentSum > maxSum) {
maxSum = currentSum;
}
}
return maxSum;
}
}
understood
// first time bro
Understood
Thanks bro, just subbed to the channel
understood
Amazing ❤
Amazing experience
but if the subarray consist of on;y negative elements , then in that case max sum should be the smallest negative element in the array ?
Striver 🔥🔥🔥🔥🔥
Thanks bhaiya 💖💖
Thank you!
def maxSubArray(nums):
max_sum = nums[0]
current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))
TQ
Awesome
You the best❤
i understood the algo and intuition as well, but after some time I am forgetting things. what shall I do
I feel the same! what are u doing??
@@striver17 I’m trying to revise as much as possible everyday
Understood!
Understood!
Hey Striver! How can I find the second maximum subarray sum in an array
❤
thanks
understood!
I understand it but I have one question like if all the elements are negative in the array then what we can do?
The smallest number as a single element will be the subarray
@@takeUforward but how to code can you please make a video , i haven't seen any video on youtube who explain about all the negative subarrays
understood♥
understood...
understood.
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.
LeetCode JAVA Solution:
class Solution {
public int maxSubArray(int[] nums) {
int max= Integer. MIN_VALUE;
int sum=0;
int c=Integer.MIN_VALUE;
for(int i=0;imax)
max=sum;
}
if(max==0)
max=c;
return max;
}
}
i have a question , if in interview we do this question like brute force then optimal , do i need to mention the algo used , won't the interviewer think why i started with brute when i knew this algo need to be used?
Usually they don't ask these questions, they want to check your solving skills. You can also tell about the algorithm without telling the name..
@@takeUforward thank you ✨
A2Z series is the Gold
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 :)
Understood !!
Understood
Understood
understood
understood
❤
Always ready for Dsa ✅
Haan Bhai
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
Printing the subarrays part is something i learn this time tysm understood:)
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.
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.
Are you using an iPad or something else?
Understood
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
Understood
Understood
#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....
Understood
Understood
Understood
Understood