Kadane's Algo in 16 minutes || Algorithms for Placements
Vložit
- čas přidán 7. 09. 2024
- In this Video, we are going to learn about Kadane's Algorithm.
There is a lot to learn, Keep in mind “ Mnn bhot karega k chor yrr apne se nahi hoga ya maza nahi aara, Just ask 1 question “ Why I started ? “
[For 20% Discount ] Visit Coding Ninjas: bit.ly/3cfdKTe
Discord Server Link: / discord
Course Flow: whimsical.com/...
Slides Link: drive.google.c...
Code Links: github.com/lov...
Questions Links:
- Kadane's Algo - leetcode.com/p...
Do provide you feedback in the comments, we are going to make it best collectively.
Connect with me here:
Instagram: / lovebabbar1
Twitter: / lovebabbar3
Telegram Group Link: Love Babbar CODE HELP
telegram.me/lo...
My Editor: www.instagram....
Intro Sequence: We have bought all the required Licenses of the Audio, Video & Animation used.
#DP_Series #LoveBabbar
When you study great teachers… you will learn much more from their caring and hard work than from their style. TQ sir
This was an amazing example sir, if we wanted we would have made this code a lot more heavier and complex. Increasing its complexity.
But your video showed us an follow process to make the code optimal and reduce the complexity to lowest possible.
i just came to your video , i am afraid about DSA , Now i just see that video and now i am confident that i can also solve the problems, your way of teaching is quite simple and easy. thanks a lot.
Nooooo one can explain better than him...Thank you Sir for such an easy explanation
so nice to see someone who can explain things just as easy as this, I understood everything concept he explained while I can speak nor hear a single word in indian language, imagine if he were speaking in English 🤣🤣, a great teacher always finds a way to make students understands what he means. Thanks India for producing such indian talents.
Even if we are asked for size of longest subarray which yields the max sum , we can use Concept of Variable size window to find the sum(mx sum using kadane ) . Time => O(n)
bhai 2 loop use karke all subarray kaise nikal sakte hai?
@@Asad-pq7el take a vector sum and intial array of size n, then
go i = 0->n, where there's a var x = 0 & max = 0
then run j = i -> n, where x += arr[j] and if arr[j] beginner than max update it and also store the i & j index in another var a,b..
after the whole iteration is completed, you'll have a, b which is the starting & finishing index of the longest subarray with max sum..
You are going to revolutnize the coding universe....💯💯
love from nepal..🥰
The playlist that I've been searching all over the internet and finally you started it.., thankyou for making it❣️
Some Nigaa Said "This was an amazing example sir, if we wanted we would have made this code a lot more heavier and complex. Increasing its complexity. But your video showed us an follow process to make the code optimal and reduce the complexity to lowest possible."
One of the most important approach for the complex problem of array.
The also doesn't work for negative numbers, You need different algorithm. Following is the working implementation in Javascript:
function maxSubArray(nums) {
let maxSoFar = nums[0];
let maxEndingHere = nums[0];
for (let i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
Bhaiya,
A suggestion for Dsa series--
Could you please create a schedule kinda like when to start when to end what ,
An excel sheet or something where we can enter our start date nd the rest dates will b decided logically for whole dsa plan ,this will give us a fair idea of which vdo/homework/tasks should take what time for completion.
We can stick to that and try to complete the course within the deadlines as mentioned in the sheet.
Problem in self is that we don't get an idea how much to do each day or how to allocate number of days to each topic,thus we exaggerate the things without proper plan leading to non completion of tasks
i agree!!
explained from basics, so best explanation ever thank uuuu😇
Simplest and BEST explaination ever! Thank you so much babbar bhaiya.
170 Bhaiya aapke ecplainations ki etni aadat hui hai ki ab baki khi se bhi padho kuch samj nahi aata
Besttesstttt explaination & Bhaiyaaaa Everrrr😍
Bhaiyya ,love the video and solution,
Please upload the lecture on-
"sliding windows algorithm"
doesnt work if all numbers in array are -ve, maxi will return a negative integer rather than returning 0.
Thank you bhaiya ....just isko sikhne ke bad maine lagatar 2 questions solve kar di with some modifications for different problems
I have gone through multiple videos none of them helped me to understand Kandane's algorithm. This video does
KMP Algorithm next pls??🙃
Han bhaiya kmp algorithm please upload the video
thankyou bhaiya for easy and to the point concept of kadane's algo.
Another game changing playlist started...kudos to you sir...DAY 1 ✅
Thank you so much sir nice explanation and easy to understand ❤️
Efforts >>>3 man ❤️
Thank You Bhaiya for Completing the Remaining Algorithms
Nice Man just opened my concepts crystal clear
Best Explanation bhaiya
Simply great explanation, great bhaiya 🔥🔥🙌🙌
Ek baar mein hi samjh aa gaya thanks mahan guru ji 😊
if all the element in the array is -ve then apply this
long long maxSubarraySum(int arr[], int n){
long long max = arr[0];
long long sum=0;
for(int i=0;imax)
max = sum;
if(sum
Wonderful explanation.... did't know that. it is that much easy.
bhoat time se wait kr Raha tha ..
Thankyou bhaiya, I understood it clearly now...😄 I wanted to ask that will us be ever able to actually make these kind of algorithms ourseleves? Like learning sliding windows, kadane's algo and other algos is different thing and making them is different.
To actually make algorithms you can do your research/phd in algorithms. These algorithms were made in budding days of computer science and algos are mainly build by mathematicians. Like this kadane algo was made in 1980s
@@rohanverma3111 Thanks for the info brother👍
@@rohanverma3111 I want to ask that do developers make algorithms or they just see it from somewhere, or learn it and only implement it?
@@sirkartik I hardly believe that any developer is building some amazing algorithms in their day to day job. No dev will write a new algo. Even if you make a decent algorithm in a project codebase on your own but it won't be approved by your seniors if some standard algo is out there. If you are interested about making algorithms you can opt for MS/PHD in CSE and can take your thesis as Algorithms. To discover new things you need to pursue research.
Thanks I was stuck at this program from last 3 days,sab ho gya tha sum
third step needs more explanation why we need to make sum 0 if sum becomes -ve anuj bhaiya have explained it well if some one does not understand please checkout his video once.
You found the sum but which sub array produced that highest sum was not shown in code. How do we highlight which sub array has the highest sum?
is this correct ? python
arr = [-1,2, 2, -3,4, -4, 5]
max = 0
current = 0
for i in arr:
current += i
if current < 0 :
current = 0
if current > max :
max = current
print(max)
print(current)
Bhaiya if possible can you start series on solving your 450 Dsa cracker sheet
If you provide a bit overview of the problem also then it will be very much helpful as your explanation is excellent
Thank you bhaiya 🙏
Yeah it's needed
Yes , it will be helpful.
Bhaiya swad aa jaata haii apki video dekh k❤💯
mst samjaya bhaiya
Doesn't work on all negative numbers. I have to search correct Kadane's also.
truly the best explaination
majaa aa gyaa bro. keep it up!!
Hello Jiii ...web development course kabhi upload honge bhaiya ?Excited to learn web development from ur end...
I understood the approach, thanks bhaiya but I am not understanding why this one is not working, I understand that this is not the efficient approach but yet, what I am doing wrong
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n=len(nums)
self.maxSum=-float('inf')
if n==0:
return 0
if n==1:
return nums[0]
def helper(nums,i,curr_sum):
if i>n-1:
self.maxSum=max(self.maxSum,curr_sum)
return curr_sum
op1=helper(nums,i+1,curr_sum+nums[i])
op2=helper(nums,i+1,nums[i])
self.maxSum=max(op1,op2)
return max(op1,op2)
helper(nums,0,0)
return self.maxSum
why are you taking sum =0 if sum
Thankuu bro... For your efforts..❤🙏
Thank you so much bhaiya😁❤️
So much love to you
most valuble content bhaiya majaa aa gya
😀😀
Bhaiya plz make videos on rabin karp algo and kmp algo
understood the concept thank you babbar bhai
Amazing explanantion.
Kudos to your hardwork 👏
thanks bhaiya you made dsa easy for me
// COMPLETE CODE
class Solution {
public:
int maxSubArray(vector& nums) {
int sum = 0;
int maxi = nums[0];
for(int i=0; i
good explanation.....How all are here after todays daily challenges at leetcode lol?
Ye bari achi initiative liya hai aapne bhaiya 👍👍
great explanation! thank you for this
Amazing Explanation Sir
Algo samjha diya apne code khud karunga😂
Sir ,
What if all the elements were negative....so in that case, how could we implement the condition for less than 0
did you get the answer ?
@@Griffith_1802 some has mentioned this code:
function maxSubArray(nums) {
let maxSoFar = nums[0];
let maxEndingHere = nums[0];
for (let i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
thank you sir
Any upcoming live web development batches? Your CZcams content has been super helpful, but I want to try a live class for a more interactive learning experience. Let me know if you have any plans or updates. Thanks!
Can anyone tell me ans for maximum subarray sum for
[2,0,7,8] using the above algorithm
please
But in the question it is asked to give the sub array too where is the sub array ?
@CodeHelp Although all the test cases passed. I don't think this code should pass the case where all the Elements are negative.
It would because the sum
You made it easy thank you 😌
for the all the negative number this approach will fail
It will work
Because each time sum become 0 as it will become negative for each iteration
Then for the greatest negative no(smallest in magnitude) sum will become equal to that no. Ans maxi will become that no. By max (sum, maxi) and that no will come output as maxi will not get updated further
Will work
Bro Just sort and print arr[0] if all negative
@@moohsinatabassum5915complexity will increase if we do that
It will work bro 😅 just update the maximum before you update the sum to 0. That's simple : )
Sliding Window Playlist is Missing, Better Add Some Video Regarding Problem Solving About Sliding Window... Unacademy Live Session Me Maja Nehi Aiya😔 Pls Babbar Bhai Last Wala Topic Cover Kar Dho..
Love From Bangladesh
Try coming to this side by illegal border crossing...
anyone explain the second approach in o(n^2) time complexity
If all the elements are negative then the max sum of contiguous subarray is not zero.
Achha lga app ka btane ka trika ♥️
if we consider all +ve integer in array then max sum should be 12
thankyou sir
sir mazza aa gya 😊
Nice explanation sir ......
If the array contains all negative integers than what will be the sum? since here u are excluding all the negative sum,,
Thanks for new vedio Babbar
Great Explanation
thank you sir 👌👌👌👌
Sir,According to me you cannot get all the subarrays from only 2 loops which you have used ! if so please anyone clear my doubt!
What if we dont need maximum sum but instead want those subpairs which make maximum sum???
can not find symbol
maxi =max(maxi , sum);
symbol: method max(int , int)
bro i am face this error please resolve this
Kudos to your effort :)
New series algorithms hurray 🙂
nice explanation
Best explanation
Segtree wen?
Best Explanation
amazing explanation!!!!!!!!!
very easily described
9:37 agar sum = -1 aya,then max(-1,-2) = -1; to hum kiu sum ko ignore kare jaab sum 0 se kam aye??
String algorithm , segment tree krwa do
Thankyou for this video bhiaya
good explanation bhaiya
Bhaiya, can you share 2nd approach with time Complexity O(N2) .I just want to cross Verify my code ...
can you pls ur code
share
Bhaiya please two pointer approach and sliding window algo ko bhi cover kr do
Sir ye to fail ho jayega na jb saare hi elements negative ho to, kyu sum =0 zero rakhoge ??
It will work for all negative elements too, do dry run once
Bhaiya sliding window ka ak video lao
sir can you please make a video on fermat little theorem and wilson theorem 🙏🙏🙏🙏🙏
10133 /10134 test cases passed...the code worked 2 months ago now its updated
what's the one exception?
Use long long as dtypes for sum and max_element variable.