Maximum Sum such that no 2 Elements are Adjacent | Love Babbar DSA Sheet | GFG | FAANG🔥 | Placement
Vložit
- čas přidán 22. 12. 2020
- #dp #sorting and searching #competitiveprogramming #coding #dsa
Hey Guys in this video I have explained with code how we can solve the problem 'Maximum Sum such that no 2 Elements are Adjacent'.
Code for O(1) Space Complexity-- www.geeksforgeeks.org/find-ma...
Array question Playlist = • Love Babbar DSA 450 Qu...
String question Playlist = • Love Babbar DSA 450 Qu...
Searching and Sorting question Playlist = • Love Babbar DSA 450 Qu...
Binary Tree question Playlist = • Love Babbar DSA 450 Qu...
Dynamic Programming question Playlist = • Love Babbar DSA 450 Qu...
Roadmap for Dynamic Programming = • Complete Roadmap for D...
Great Strategy to solve DSA = • Great Strategy to solv...
My Journey to 5 star at codechef = • My Journey to 5 Star a...
Love Babbar DSA Sheet : drive.google.com/file/d/1FMdN...
Follow us on Instagram:
Shailesh Yogendra : / shaileshyogendra
Yogesh Yogendra : / i_am_yogesh_here
Follow us on Linkedin:
Shailesh Yogendra : / shailesh-yogendra-8b13...
Yogesh Yogendra : / yogesh-yogendra-26bbb518a
Hope you like it. Comment if you have any doubt
LIKE | SHARE | SUBSCRIBE
Thanku so much sir for your efforts for us 💖💖
keep up the great work
thanks for the detailed explaination
Very nice vedio bhaiya, very much helpful.
Good one
how do u erase the prewritten driver code on the gfg IDE and write your code from scratch. PLEASE REPLY BRO. EVERYONE WANTS TO KNOW
Actually when I was doing this question then there were no driver code....but now they have updated the code snippet and added the driver code
Thanks
thanks
Ekdum mst kiye explain🙏🙏
😍😍😍😍😍😍😍😍😍
amazing 👌👌
Thanks a lot 😊
i did a recursion based approach , but was unable to optimise it ,got the states on where it is repeating for memoisaiton, 2 d array, one dimension is the sum till now, and another is its index(10^5 is the highest number ig), another dimension is the index, (10^5 is the highest ig), so 10^5 and 10^5 array is possible ? can it be used to memoise the solution and optimise it?
See my recursive solution --> submitted on gfg
class Solution
{
int dp[10000][2];
// finds the max sum if the element is taken.
int findmax(int arr[], int ind, bool state, int n){
if(ind == n-1) return state ? arr[ind] : 0;
if(ind >= n) return 0;
if(state){
// if we are taking that index --> then we can or cannot take the i+2 th element.
if(dp[ind][1]!= -1) return dp[ind][1];
int left= findmax(arr, ind+2, true, n);
int right= findmax(arr, ind+2, false, n);
return dp[ind][1] = max(left, right) + arr[ind];
}
if(dp[ind][0]!= -1) return dp[ind][0];
int leftt= findmax(arr, ind+1, true, n);
int rightt= findmax(arr, ind+1, false, n);
return dp[ind][0]= max(leftt, rightt);
}
public:
int FindMaxSum(int arr[], int n)
{
memset(dp, -1, sizeof(dp));
// taking 0 and not taking 0
return max(findmax(arr, 0, true, n), findmax(arr, 0, false, n));
}
};
int max=Integer.MIN_VALUE;
if(n==0) return 0;
int value1=arr[0];
if(n==1) return value1;
int value2=Math.max(arr[0],arr[1]);
if(n==2) return value2;
for(int i=2;i
Yogesh bhai aap hi video dala karo aapka samjh aata hai , bakio se nhi ho para , they know there stuff , but they dont have the teaching sence
how is the time complexity O(n)? Here we are memoizing to O(n^2) from O(2^n)..... I'm confused , can anyone help me out.
The recursion tree (without memoization) has a many overlapping subproblems. Therefore, instead of calling solve(index val, a) repetitively, we are first checking if solve(index val, a) is present in dp array or not. If it is present, we directly return without making further recursion calls. Hence, we are calling solve(index val, a) for each index of "a" only once, making the time complexity O(N). Refer: www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/
how do you remove the existing code??
Bro great video...but how do u erase the prewritten driver code on the gfg IDE and write your code from scratch
you all prolly dont give a damn but does anybody know of a method to get back into an instagram account..?
I was dumb forgot the password. I would love any assistance you can give me
@Gianni Ellis instablaster ;)
@Brentley Randy I really appreciate your reply. I got to the site thru google and im trying it out now.
I see it takes quite some time so I will get back to you later with my results.
@Brentley Randy it did the trick and I finally got access to my account again. I am so happy!
Thank you so much, you saved my ass !
@Gianni Ellis You are welcome :D
bhai iska greedy sol hai to koi link share kar do yaha pe plz
Bro wo O(1) space complexity wala solution smj nehi a raha hai
Plz make a vedio on it
Or if anyone knows it then plz comment pe batana
I'm getting TLE.
bhai apne code ka link share kar diya karo yrr
this problem was under sorting and searching right? why are we using dp? i haven't learned dp yet so this is all just gibberish to me :(
Ye question dp ka hi tha...but it's Given under searching sorting 😂
Bhai Aditya verma ki DP series dekh lo, muje pehle recursion aur DP aata nhi tha, ab to me aaram se medium difficulty wala dp questions solve kar leta hu
@@anonymous-ip9rn ok bro, thanks
@Rohit Gupta yeah bro, i couldn't do most string questions for the same reason.. And as of this question, a solution without DP also exists, check that out
@@CodeLibrary 😂😂