title

DP 5. Maximum Sum of Non-Adjacent Elements | House Robber | 1-D | DP on Subsequences

description

Lecture Notes/C++/Java Codes: https://takeuforward.org/data-structure/maximum-sum-of-non-adjacent-elements-dp-5/
Problem Link: https://bit.ly/3q5rlUY
Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward
Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9
Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY
In this video, we have discussed how to solve the problem of the maximum sum without taking adjacent elements. Here the concept of pick non pick has been explained.
If you have not yet checked our SDE sheet, you should definitely do it: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
You can also get in touch with me at my social handles: https://linktr.ee/takeUforward

detail

{'title': 'DP 5. Maximum Sum of Non-Adjacent Elements | House Robber | 1-D | DP on Subsequences', 'heatmap': [{'end': 487.928, 'start': 465.156, 'weight': 1}, {'end': 1110.744, 'start': 1085.645, 'weight': 0.701}, {'end': 1264.683, 'start': 1238.7, 'weight': 0.772}, {'end': 1501.391, 'start': 1477.398, 'weight': 0.836}], 'summary': 'Covers dynamic programming concepts including finding maximum sum of non-adjacent elements, using recursion and memoization to optimize time complexity, and implementing tabulation and space optimization for improved efficiency in handling test cases.', 'chapters': [{'end': 37.503, 'segs': [{'end': 37.503, 'src': 'embed', 'start': 0.149, 'weight': 0, 'content': [{'end': 1.37, 'text': 'hey, everyone, welcome back to the channel.', 'start': 0.149, 'duration': 1.221}, {'end': 3.212, 'text': 'i hope you guys are doing extremely well.', 'start': 1.37, 'duration': 1.842}, {'end': 7.055, 'text': 'so welcome to the fourth lecture of dynamic programming playlist.', 'start': 3.212, 'duration': 3.843}, {'end': 8.176, 'text': 'what is the problem?', 'start': 7.055, 'duration': 1.121}, {'end': 17.485, 'text': "today's problem is going to be maximum sum of non-adjacent elements again one kind of one ddp that we will be solving.", 'start': 8.176, 'duration': 9.309}, {'end': 18.926, 'text': "i'll be following the same pattern.", 'start': 17.485, 'duration': 1.441}, {'end': 25.252, 'text': "you might have solved this problem previously, but the way i'll be teaching you will be something very, very, very different.", 'start': 18.926, 'duration': 6.326}, {'end': 29.656, 'text': 'so please, please do watch the video till the end to understand all the logic.', 'start': 25.652, 'duration': 4.004}, {'end': 32.118, 'text': "don't think that if you understand memorization, it's done.", 'start': 29.656, 'duration': 2.462}, {'end': 33.519, 'text': 'you have to understand tabulation.', 'start': 32.118, 'duration': 1.401}, {'end': 37.503, 'text': 'you have to understand space optimization in order to be the best.', 'start': 33.519, 'duration': 3.984}], 'summary': 'Lecture on solving dynamic programming problem for maximum sum of non-adjacent elements, emphasizing unique teaching approach.', 'duration': 37.354, 'max_score': 0.149, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY149.jpg'}], 'start': 0.149, 'title': 'Maximum sum of non-adjacent elements', 'summary': 'Covers the fourth lecture of the dynamic programming playlist, emphasizing the importance of understanding memorization, tabulation, and space optimization to solve the problem of finding the maximum sum of non-adjacent elements.', 'chapters': [{'end': 37.503, 'start': 0.149, 'title': 'Dynamic programming lecture 4: maximum sum of non-adjacent elements', 'summary': 'Covers the fourth lecture of the dynamic programming playlist, focusing on solving the problem of finding the maximum sum of non-adjacent elements with a unique teaching approach, emphasizing the importance of understanding memorization, tabulation, and space optimization.', 'duration': 37.354, 'highlights': ['The lecture focuses on solving the problem of finding the maximum sum of non-adjacent elements using a unique teaching approach.', 'The importance of understanding memorization, tabulation, and space optimization for mastering dynamic programming is emphasized.', 'The video encourages viewers to watch till the end to grasp the different logic presented in the lecture.']}], 'duration': 37.354, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY149.jpg', 'highlights': ['The lecture focuses on solving the problem of finding the maximum sum of non-adjacent elements using a unique teaching approach.', 'The importance of understanding memorization, tabulation, and space optimization for mastering dynamic programming is emphasized.', 'The video encourages viewers to watch till the end to grasp the different logic presented in the lecture.']}, {'end': 232.489, 'segs': [{'end': 82.952, 'src': 'embed', 'start': 37.503, 'weight': 0, 'content': [{'end': 40.286, 'text': "okay, so let's, let's understand the question.", 'start': 37.503, 'duration': 2.783}, {'end': 43.669, 'text': 'basically, it states you will be given an array of n integers.', 'start': 40.286, 'duration': 3.383}, {'end': 46.652, 'text': "that means you're given an array which consists of n integers.", 'start': 43.669, 'duration': 2.983}, {'end': 50.976, 'text': "okay, so you're supposed to return the maximum sum of the subsequence.", 'start': 46.652, 'duration': 4.324}, {'end': 56.698, 'text': 'Now, remember, you have to pick up a subsequence which gives you a maximum sum.', 'start': 51.576, 'duration': 5.122}, {'end': 57.598, 'text': 'but there is a constraint.', 'start': 56.698, 'duration': 0.9}, {'end': 63.039, 'text': 'In the subsequence, none of the elements can be adjacent from the array.', 'start': 58.138, 'duration': 4.901}, {'end': 73.412, 'text': "So, for an example, if I look on this test case, which is 1, 2, 4, you can't pick something like 1, 2, or you can't pick something like 2,", 'start': 64.099, 'duration': 9.313}, {'end': 74.723, 'text': '4 because they are adjacent.', 'start': 73.412, 'duration': 1.311}, {'end': 75.704, 'text': 'got it.', 'start': 75.063, 'duration': 0.641}, {'end': 79.889, 'text': 'so probably you can pick something like one and four, which gives you the maximum sum.', 'start': 75.704, 'duration': 4.185}, {'end': 82.952, 'text': "five. that's what the maximum sum will be like over here.", 'start': 79.889, 'duration': 3.063}], 'summary': 'Given an array, find maximum sum of non-adjacent subsequence.', 'duration': 45.449, 'max_score': 37.503, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY37503.jpg'}, {'end': 206.776, 'src': 'embed', 'start': 143.367, 'weight': 1, 'content': [{'end': 147.669, 'text': "i'm gonna try out all sub sequences and whichever sub sequences gives you the maximum sum.", 'start': 143.367, 'duration': 4.302}, {'end': 149.17, 'text': "we're gonna pick that one.", 'start': 147.669, 'duration': 1.501}, {'end': 150.671, 'text': 'as simple as that.', 'start': 149.17, 'duration': 1.501}, {'end': 158.135, 'text': 'now the question arises whenever we say trying out all stuff, what comes to your brain?', 'start': 150.671, 'duration': 7.464}, {'end': 162.037, 'text': 'obviously one thing comes to your brain, which is recursion.', 'start': 158.135, 'duration': 3.902}, {'end': 170.021, 'text': "so you're gonna try out recursion correct, and after that we are going to see if there are overlapping sub problems and that's, that's.", 'start': 162.037, 'duration': 7.984}, {'end': 171.082, 'text': "that's for the remaining part.", 'start': 170.021, 'duration': 1.061}, {'end': 171.762, 'text': 'but we have.', 'start': 171.082, 'duration': 0.68}, {'end': 173.022, 'text': 'we have understood that.', 'start': 171.762, 'duration': 1.26}, {'end': 173.862, 'text': 'why recursion?', 'start': 173.022, 'duration': 0.84}, {'end': 180.744, 'text': "because if they're asking you to try out all sub sequences, we have to, and that is only doable by recursion.", 'start': 173.862, 'duration': 6.882}, {'end': 183.244, 'text': 'so how do you print all sub sequences?', 'start': 180.744, 'duration': 2.5}, {'end': 185.285, 'text': "that's, that's a big question.", 'start': 183.244, 'duration': 2.041}, {'end': 189.525, 'text': 'uh, before, uh, solving this question, how do you print all sub sequences?', 'start': 185.285, 'duration': 4.24}, {'end': 194.107, 'text': "so there's a technique which is known as pick and non-pick.", 'start': 189.525, 'duration': 4.582}, {'end': 202.973, 'text': 'okay. so i have taught this entire technique in lecture six of recursion series and a lecture seven in depth.', 'start': 194.107, 'duration': 8.866}, {'end': 206.776, 'text': "so if you haven't seen both of the lectures, pause it right now.", 'start': 202.973, 'duration': 3.803}], 'summary': 'Use recursion to find maximum sum subsequence, employing pick and non-pick technique.', 'duration': 63.409, 'max_score': 143.367, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY143367.jpg'}], 'start': 37.503, 'title': 'Maximum sum of non-adjacent subsequence', 'summary': 'Explains finding the maximum sum of a subsequence from an array of n integers by not picking adjacent elements, with an example of achieving a maximum sum of 11. it also discusses the approach of trying out all subsequences using recursion and the pick and non-pick technique, emphasizing the need for recursion and the logic behind printing all subsequences.', 'chapters': [{'end': 102.648, 'start': 37.503, 'title': 'Maximum sum of non-adjacent subsequence', 'summary': 'Explains how to find the maximum sum of a subsequence from an array of n integers by not picking adjacent elements, with an example of achieving a maximum sum of 11.', 'duration': 65.145, 'highlights': ["You will be given an array of n integers and you're supposed to return the maximum sum of the subsequence, where none of the elements can be adjacent from the array.", 'The maximum sum of the subsequence can be achieved by picking up non-adjacent elements, illustrated with an example of achieving a maximum sum of 11 from the given array.', 'The constraint requires the selection of elements in a subsequence such that none of them are adjacent from the array.']}, {'end': 232.489, 'start': 102.648, 'title': 'Recursion and pick and non-pick technique', 'summary': 'Discusses the approach of trying out all subsequences using recursion and the pick and non-pick technique, emphasizing the need for recursion and the logic behind printing all subsequences.', 'duration': 129.841, 'highlights': ['The technique of trying out all subsequences using recursion and picking the one with the maximum sum is emphasized.', 'The importance of recursion in trying out all subsequences is highlighted, explaining the need for recursion in solving the problem.', 'The pick and non-pick technique for printing all subsequences is stressed, directing viewers to lectures six and seven for a detailed understanding.']}], 'duration': 194.986, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY37503.jpg', 'highlights': ['The maximum sum of the subsequence can be achieved by picking up non-adjacent elements, illustrated with an example of achieving a maximum sum of 11 from the given array.', 'The technique of trying out all subsequences using recursion and picking the one with the maximum sum is emphasized.', 'The importance of recursion in trying out all subsequences is highlighted, explaining the need for recursion in solving the problem.', 'The pick and non-pick technique for printing all subsequences is stressed, directing viewers to lectures six and seven for a detailed understanding.', "You will be given an array of n integers and you're supposed to return the maximum sum of the subsequence, where none of the elements can be adjacent from the array.", 'The constraint requires the selection of elements in a subsequence such that none of them are adjacent from the array.']}, {'end': 680.093, 'segs': [{'end': 267.214, 'src': 'embed', 'start': 232.489, 'weight': 0, 'content': [{'end': 236.99, 'text': 'express every recursion in terms of indexes.', 'start': 232.489, 'duration': 4.501}, {'end': 238.891, 'text': 'okay, makes sense.', 'start': 236.99, 'duration': 1.901}, {'end': 242.912, 'text': 'do stuffs on that index.', 'start': 238.891, 'duration': 4.021}, {'end': 251.184, 'text': 'okay, do stuffs on that index, then return the best that you can get return the best that you can get.', 'start': 242.912, 'duration': 8.272}, {'end': 253.625, 'text': 'that is something which i know now over here.', 'start': 251.184, 'duration': 2.441}, {'end': 255.146, 'text': 'what is the problem?', 'start': 253.625, 'duration': 1.521}, {'end': 260.108, 'text': 'pick subsequence with no adjacent.', 'start': 255.146, 'duration': 4.962}, {'end': 264.652, 'text': 'remember this, with no adjacent elements.', 'start': 260.108, 'duration': 4.544}, {'end': 267.214, 'text': 'so where do you pick?', 'start': 264.652, 'duration': 2.562}], 'summary': 'Recursively process indexes to pick non-adjacent subsequences.', 'duration': 34.725, 'max_score': 232.489, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY232489.jpg'}, {'end': 318.86, 'src': 'embed', 'start': 291.163, 'weight': 2, 'content': [{'end': 294.144, 'text': 'because i know how to print all the subsequences.', 'start': 291.163, 'duration': 2.981}, {'end': 298.685, 'text': 'but now there is a constraint which states with no adjacent elements, right.', 'start': 294.144, 'duration': 4.541}, {'end': 302.267, 'text': 'so we want the maximum sum, correct.', 'start': 299.665, 'duration': 2.602}, {'end': 311.454, 'text': 'so can i say our recursion to define something like this f of index states the maximum sum,', 'start': 302.267, 'duration': 9.187}, {'end': 318.86, 'text': 'like the maximum sum that you can get if you pick a subsequence from the index 0 till the index.', 'start': 311.454, 'duration': 7.406}], 'summary': 'Determining maximum sum of subsequences with no adjacent elements using recursion.', 'duration': 27.697, 'max_score': 291.163, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY291163.jpg'}, {'end': 494.694, 'src': 'heatmap', 'start': 465.156, 'weight': 1, 'content': [{'end': 471.06, 'text': "if I decide that I'm not going to pick, if I'm not picking an index, can I pick an index minus one?", 'start': 465.156, 'duration': 5.904}, {'end': 472.061, 'text': 'make sense?', 'start': 471.06, 'duration': 1.001}, {'end': 477.265, 'text': 'so I will say okay, I will pick up the index right now.', 'start': 472.061, 'duration': 5.204}, {'end': 477.765, 'text': 'can I see?', 'start': 477.265, 'duration': 0.5}, {'end': 487.928, 'text': 'this is for the current, and the sum from index minus two, 0 will be given by this recurrence.', 'start': 477.765, 'duration': 10.163}, {'end': 494.694, 'text': 'so this plus, this will be the sum that you will get from 0 till index.', 'start': 487.928, 'duration': 6.766}], 'summary': 'Discussing index selection and sum calculation for a given range.', 'duration': 29.538, 'max_score': 465.156, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY465156.jpg'}, {'end': 680.093, 'src': 'embed', 'start': 614.829, 'weight': 1, 'content': [{'end': 616.149, 'text': 'so there will be couple of base cases.', 'start': 614.829, 'duration': 1.32}, {'end': 619.952, 'text': "we have to think on this and there's no, not pick and pick.", 'start': 616.149, 'duration': 3.803}, {'end': 632.329, 'text': "so in this way i have modulated the subsequence code that i've taught you in the lecture six in order to write a similar problem with an additional no-adjacent constraint.", 'start': 619.952, 'duration': 12.377}, {'end': 634.59, 'text': 'So, I hope you have understood the recurrence.', 'start': 632.849, 'duration': 1.741}, {'end': 636.571, 'text': "It's pretty straightforward.", 'start': 634.75, 'duration': 1.821}, {'end': 639.852, 'text': "So, if you talk about this recurrence, you're going to try out all the possible ways.", 'start': 636.871, 'duration': 2.981}, {'end': 645.614, 'text': "The time complexity is definitely exponential, which is 2 to the power n, because you'll try out all.", 'start': 640.192, 'duration': 5.422}, {'end': 647.214, 'text': "It's not exactly 2 to the power n.", 'start': 645.614, 'duration': 1.6}, {'end': 648.295, 'text': "It's going to be lesser than that.", 'start': 647.214, 'duration': 1.081}, {'end': 650.776, 'text': 'So, you have to memoize it.', 'start': 648.875, 'duration': 1.901}, {'end': 658.196, 'text': 'Now, now question arises how do you optimize recursion?', 'start': 651.236, 'duration': 6.96}, {'end': 662.619, 'text': 'you have to figure out if the recursion has overlapping subproblems.', 'start': 658.196, 'duration': 4.423}, {'end': 668.124, 'text': 'like, if the recursion has overlapping subproblems, then we can definitely memoize it right.', 'start': 662.619, 'duration': 5.505}, {'end': 670.325, 'text': 'so it will have overlapping subproblems.', 'start': 668.124, 'duration': 2.201}, {'end': 678.412, 'text': "so what we will do is we'll take a very simple example 2, 1, 4, 9, and i'll write the index numbers as 0, 1, 2, 3.", 'start': 670.325, 'duration': 8.087}, {'end': 680.093, 'text': "let's start from f of 3,", 'start': 678.412, 'duration': 1.681}], 'summary': 'Modulated subsequence code with no-adjacent constraint, exponential time complexity of 2^n, need for memoization', 'duration': 65.264, 'max_score': 614.829, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY614829.jpg'}], 'start': 232.489, 'title': 'Recursion and maximum sum', 'summary': 'Discusses using recursion to find the maximum sum of a subsequence with no adjacent elements in an array, emphasizing the importance of indexing and the need to satisfy constraints for the maximum sum. it also explains the approach to optimize the subsequence problem through a modified recurrence with a no-adjacent constraint, with exponential time complexity of 2 to the power n, but can be reduced through memoization of overlapping subproblems.', 'chapters': [{'end': 371.567, 'start': 232.489, 'title': 'Recursion and maximum sum', 'summary': 'Discusses using recursion to find the maximum sum of a subsequence with no adjacent elements in an array, emphasizing the importance of indexing and the need to satisfy constraints for the maximum sum.', 'duration': 139.078, 'highlights': ['The recursion is based on the index, and the constraint of no adjacent elements is emphasized, aiming to find the maximum sum, thus ensuring the satisfaction of the first property and addressing the constraint effectively.', 'The function f of index defines the maximum sum that can be obtained by picking a subsequence with no adjacent elements from 0 to index, demonstrating the systematic approach to address the problem and find the maximum sum.', 'The importance of indexing is highlighted, and the need to satisfy constraints, such as ensuring no adjacent elements in the subsequence, is emphasized, aligning with the systematic approach to recursion and the goal of finding the maximum sum.']}, {'end': 680.093, 'start': 372.068, 'title': 'Optimizing subsequence problem', 'summary': 'Explains the approach to optimize the subsequence problem through a modified recurrence with a no-adjacent constraint, with exponential time complexity of 2 to the power n, but can be reduced through memoization of overlapping subproblems.', 'duration': 308.025, 'highlights': ['The chapter details the approach to optimize the subsequence problem by introducing a no-adjacent constraint and modifying the recurrence, resulting in an exponential time complexity of 2 to the power n, which can be reduced through memoization of overlapping subproblems.', 'The speaker discusses the constraint of not picking adjacent elements in the subsequence problem, leading to the modification of the recurrence by directly going to index minus 2 instead of index minus 1 and handling base cases.', 'Explaining the approach to optimize the subsequence problem by memoizing overlapping subproblems, the speaker emphasizes the need to identify overlapping subproblems and provides an example to illustrate the process.']}], 'duration': 447.604, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY232489.jpg', 'highlights': ['The recursion is based on the index, emphasizing the constraint of no adjacent elements', 'The approach optimizes the subsequence problem through a modified recurrence with exponential time complexity', 'The function f of index defines the maximum sum obtained by picking a subsequence with no adjacent elements', 'The importance of indexing is highlighted, aligning with the systematic approach to recursion', 'The need to satisfy constraints, such as ensuring no adjacent elements, is emphasized', 'The chapter details the approach to optimize the subsequence problem by introducing a no-adjacent constraint', 'The speaker discusses the constraint of not picking adjacent elements in the subsequence problem', 'Explaining the approach to optimize the subsequence problem by memoizing overlapping subproblems']}, {'end': 1228.833, 'segs': [{'end': 706.175, 'src': 'embed', 'start': 680.093, 'weight': 1, 'content': [{'end': 691.423, 'text': 'where f of 3 basically states is what is the maximum sum you can get you if you pick up a sub sequence with no adjacent from the index 0 to index 3,', 'start': 680.093, 'duration': 11.33}, {'end': 693.705, 'text': 'which essentially means the entire array?', 'start': 691.423, 'duration': 2.282}, {'end': 696.268, 'text': 'what is the maximum sum if you pick from this?', 'start': 693.705, 'duration': 2.563}, {'end': 701.673, 'text': 'so f of 3 is basically stating hey listen, I can definitely pick up.', 'start': 696.268, 'duration': 5.405}, {'end': 703.094, 'text': 'I can definitely pick up.', 'start': 702.314, 'duration': 0.78}, {'end': 706.175, 'text': 'So if I pick up, I will go to the F of 1.', 'start': 703.414, 'duration': 2.761}], 'summary': 'Find the maximum sum of non-adjacent subsequence from index 0 to 3.', 'duration': 26.082, 'max_score': 680.093, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY680093.jpg'}, {'end': 1062.636, 'src': 'embed', 'start': 1038.164, 'weight': 0, 'content': [{'end': 1044.708, 'text': 'and whatever the answer for f of 1 is computed once, that can be reused because answer will never change for a particular set of array.', 'start': 1038.164, 'duration': 6.544}, {'end': 1045.689, 'text': "correct? that's all.", 'start': 1044.708, 'duration': 0.981}, {'end': 1050.471, 'text': "that's how we that there are overlapping subproblems and how did the recursion work?", 'start': 1045.689, 'duration': 4.782}, {'end': 1059.254, 'text': 'So now we can easily apply memoization to it and we can reduce the time complexity, because what would be the memoization technique?', 'start': 1050.711, 'duration': 8.543}, {'end': 1061.095, 'text': 'Obviously, how many states are there?', 'start': 1059.795, 'duration': 1.3}, {'end': 1062.636, 'text': 'F of three, F of one.', 'start': 1061.255, 'duration': 1.381}], 'summary': 'Applying memoization to reduce time complexity by reusing computed answers.', 'duration': 24.472, 'max_score': 1038.164, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1038164.jpg'}, {'end': 1110.744, 'src': 'heatmap', 'start': 1085.645, 'weight': 0.701, 'content': [{'end': 1093.128, 'text': 'if dp of index is not equal to minus one, you return dp of index.', 'start': 1085.645, 'duration': 7.483}, {'end': 1103.424, 'text': 'so if you just write these couple of steps, what will happen is it will change it to a time complexity of big O of n instead of the exponential one.', 'start': 1093.128, 'duration': 10.296}, {'end': 1110.744, 'text': 'And the space complexity will change to big O of n stack space and a big O of n space.', 'start': 1103.744, 'duration': 7}], 'summary': 'Optimizing the algorithm reduces time complexity to o(n) and space complexity to o(n).', 'duration': 25.099, 'max_score': 1085.645, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1085645.jpg'}, {'end': 1140.536, 'src': 'embed', 'start': 1110.744, 'weight': 2, 'content': [{'end': 1113.245, 'text': 'so that is what the memoiation time.', 'start': 1110.744, 'duration': 2.501}, {'end': 1114.986, 'text': 'complexity is still.', 'start': 1113.245, 'duration': 1.741}, {'end': 1118.067, 'text': 'but there is still a recursion stack space which we have to omit.', 'start': 1114.986, 'duration': 3.081}, {'end': 1120.848, 'text': "but before that, let's code this up and submit this.", 'start': 1118.067, 'duration': 2.781}, {'end': 1123.429, 'text': 'so can i say n will be nothing but nums, dot size?', 'start': 1120.848, 'duration': 2.581}, {'end': 1124.629, 'text': 'i definitely can.', 'start': 1123.429, 'duration': 1.2}, {'end': 1126.53, 'text': "so let's keep it as that way.", 'start': 1124.629, 'duration': 1.901}, {'end': 1133.312, 'text': 'and can i say i will return a function which will have initially start from the last index, which is this, and we can definitely, uh,', 'start': 1126.53, 'duration': 6.782}, {'end': 1134.833, 'text': 'carry the nums with that.', 'start': 1133.312, 'duration': 1.521}, {'end': 1137.454, 'text': 'so we can surely write this and over here.', 'start': 1134.833, 'duration': 2.621}, {'end': 1140.536, 'text': 'we can write the function which is int f.', 'start': 1137.454, 'duration': 3.082}], 'summary': 'Discussing coding and recursion for handling nums with function int f.', 'duration': 29.792, 'max_score': 1110.744, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1110744.jpg'}, {'end': 1208.146, 'src': 'embed', 'start': 1182.708, 'weight': 3, 'content': [{'end': 1194.016, 'text': "if you don't pick, you will simply go to index minus 1 with the nums correct and at the end of the day you can say return max of pick and not pick.", 'start': 1182.708, 'duration': 11.308}, {'end': 1201.642, 'text': "so if i try to run this so you see all the test cases running, but if i submit this you'll get a tle.", 'start': 1194.016, 'duration': 7.626}, {'end': 1205.685, 'text': "so let's quickly, uh, quickly, have a dp array.", 'start': 1201.642, 'duration': 4.043}, {'end': 1208.146, 'text': "so it's a dp vector of now.", 'start': 1205.685, 'duration': 2.461}], 'summary': 'Implement a dynamic programming solution to avoid time limit exceeded (tle) when running test cases.', 'duration': 25.438, 'max_score': 1182.708, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1182708.jpg'}], 'start': 680.093, 'title': 'Dynamic programming and memoization', 'summary': 'Covers dynamic programming for finding maximum sum subsequence with no adjacent elements, demonstrating time complexity reduction to o(n). it also explores memoization for optimizing recursion stack space in coding problems, emphasizing improved efficiency in handling test cases through dynamic programming.', 'chapters': [{'end': 1110.744, 'start': 680.093, 'title': 'Max sum subsequence', 'summary': 'Explains the dynamic programming approach to find the maximum sum of a subsequence with no adjacent elements, demonstrating overlapping subproblems and the application of memoization to reduce time complexity to o(n).', 'duration': 430.651, 'highlights': ['The maximum sum of a subsequence with no adjacent elements is computed using dynamic programming, with the example of finding the maximum sum from index 0 to index 3, yielding a result of 11.', 'Detailed explanation of the recursive approach to computing f(3) and the overlapping subproblems encountered, leading to the understanding of memoization to optimize time complexity.', 'The process of applying memoization to the dynamic programming solution is explained, highlighting the creation of an array for storing computed values and the significant reduction in time complexity to O(n).']}, {'end': 1228.833, 'start': 1110.744, 'title': 'Memoization for recursion in coding', 'summary': 'Introduces memoization to optimize the recursion stack space in coding problems, illustrating the process with a specific coding example and highlighting the importance of using dynamic programming to further optimize the solution, leading to improved efficiency in handling test cases.', 'duration': 118.089, 'highlights': ['The chapter introduces the concept of memoization to optimize recursion stack space in coding, which is illustrated through the process of coding a specific example using memoization.', 'The importance of using dynamic programming to optimize the solution further and improve efficiency in handling test cases is emphasized.', 'The process involves utilizing a recursive function, handling base cases, and implementing memoization to store and reuse computed results, ultimately leading to a more efficient solution.']}], 'duration': 548.74, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY680093.jpg', 'highlights': ['The process of applying memoization to the dynamic programming solution is explained, highlighting the creation of an array for storing computed values and the significant reduction in time complexity to O(n).', 'The maximum sum of a subsequence with no adjacent elements is computed using dynamic programming, with the example of finding the maximum sum from index 0 to index 3, yielding a result of 11.', 'The chapter introduces the concept of memoization to optimize recursion stack space in coding, which is illustrated through the process of coding a specific example using memoization.', 'The importance of using dynamic programming to optimize the solution further and improve efficiency in handling test cases is emphasized.', 'Detailed explanation of the recursive approach to computing f(3) and the overlapping subproblems encountered, leading to the understanding of memoization to optimize time complexity.']}, {'end': 1493.987, 'segs': [{'end': 1271.026, 'src': 'heatmap', 'start': 1238.7, 'weight': 0, 'content': [{'end': 1244.804, 'text': "Instead of that, please use the pre-stored value because we're not going to any further do recursion calls and increase our time complexity.", 'start': 1238.7, 'duration': 6.104}, {'end': 1247.826, 'text': 'So if I now run this, you will see this running perfectly.', 'start': 1245.164, 'duration': 2.662}, {'end': 1253.799, 'text': "And if I submit this, You'll see it is working absolutely fine.", 'start': 1249.647, 'duration': 4.152}, {'end': 1255.98, 'text': 'So we have learned about the memoization.', 'start': 1254.379, 'duration': 1.601}, {'end': 1260.121, 'text': 'What is the next step that I generally teach? You guessed it correctly.', 'start': 1256.8, 'duration': 3.321}, {'end': 1261.522, 'text': "We're going to learn the tabulation.", 'start': 1260.461, 'duration': 1.061}, {'end': 1264.683, 'text': "Yes, we're going to convert the memoization into tabulation.", 'start': 1262.122, 'duration': 2.561}, {'end': 1267.744, 'text': 'Step one, declare the DP array of the same size.', 'start': 1265.083, 'duration': 2.661}, {'end': 1271.026, 'text': 'And you can fill that with zeros or whatever you wish to.', 'start': 1268.965, 'duration': 2.061}], 'summary': 'Learned memoization, now moving to tabulation for dp array.', 'duration': 41.753, 'max_score': 1238.7, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1238700.jpg'}, {'end': 1366.832, 'src': 'embed', 'start': 1321.941, 'weight': 3, 'content': [{'end': 1324.302, 'text': 'basically, Whenever there is a negative index encountered.', 'start': 1321.941, 'duration': 2.361}, {'end': 1331.457, 'text': "I'll add 0 just just for understanding purpose so both the base cases have been assigned and Now, let's look at the next portion.", 'start': 1324.382, 'duration': 7.075}, {'end': 1336.979, 'text': "What's the next portion? Where does, like, if index is passed on 0, it stops over here.", 'start': 1331.557, 'duration': 5.422}, {'end': 1339.34, 'text': 'If index is passed on 1, it goes.', 'start': 1337.619, 'duration': 1.721}, {'end': 1341.001, 'text': 'If index is passed on 2, it goes.', 'start': 1339.7, 'duration': 1.301}, {'end': 1343.141, 'text': 'So, you know this, that.', 'start': 1341.421, 'duration': 1.72}, {'end': 1349.624, 'text': "What is tabulation? Tabulation, by repetition, I've been saying it is bottom up.", 'start': 1343.882, 'duration': 5.742}, {'end': 1351.145, 'text': 'So, from bottom to up.', 'start': 1349.924, 'duration': 1.221}, {'end': 1353.205, 'text': "What is the base case? It's 0.", 'start': 1351.765, 'duration': 1.44}, {'end': 1354.806, 'text': "So, from 0, you'll start building.", 'start': 1353.205, 'duration': 1.601}, {'end': 1355.566, 'text': "So, 0 you've built.", 'start': 1354.846, 'duration': 0.72}, {'end': 1357.247, 'text': "So, you'll start from 1.", 'start': 1355.606, 'duration': 1.641}, {'end': 1360.25, 'text': 'So, quickly start from 1.', 'start': 1357.247, 'duration': 3.003}, {'end': 1366.832, 'text': "And you can go on till end i++, correct? Now, what is the take case? Let's write the take case.", 'start': 1360.25, 'duration': 6.582}], 'summary': 'Explanation of tabulation technique for building from base case 0 to take case', 'duration': 44.891, 'max_score': 1321.941, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1321941.jpg'}, {'end': 1420.443, 'src': 'embed', 'start': 1394.469, 'weight': 4, 'content': [{'end': 1401.612, 'text': 'And dp of i will be max of take and non-take.', 'start': 1394.469, 'duration': 7.143}, {'end': 1404.578, 'text': 'Do you agree with me? You have to.', 'start': 1402.557, 'duration': 2.021}, {'end': 1408.279, 'text': "There's absolutely no other option, right? So everyone has agreed with this.", 'start': 1404.598, 'duration': 3.681}, {'end': 1409.8, 'text': 'Now I see an edge case.', 'start': 1408.779, 'duration': 1.021}, {'end': 1420.443, 'text': 'What is the edge case? The edge case states if dp, like i minus 2, for an example, whenever i is 1, so 1 minus 2, this will go to a negative index.', 'start': 1409.88, 'duration': 10.563}], 'summary': 'The maximum of take and non-take will be dp of i. an edge case occurs when i is 1, leading to a negative index.', 'duration': 25.974, 'max_score': 1394.469, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1394469.jpg'}], 'start': 1229.273, 'title': 'Tabulation in dynamic programming', 'summary': 'Discusses converting memoization into tabulation in dynamic programming, emphasizing pre-stored values to optimize time complexity, explaining the bottom-up approach of tabulation, and addressing edge cases and negative indices.', 'chapters': [{'end': 1343.141, 'start': 1229.273, 'title': 'Tabulation and memoization', 'summary': 'Discusses the process of converting memoization into tabulation in dynamic programming, emphasizing the importance of pre-stored values to optimize time complexity and demonstrating base case handling and index traversal for efficient computation.', 'duration': 113.868, 'highlights': ['The importance of pre-stored values to optimize time complexity is emphasized, reducing the need for further recursion calls and increasing efficiency.', 'The process of converting memoization into tabulation is discussed, involving the declaration of a DP array of the same size and filling it with zeros, followed by handling base cases and index traversal for efficient computation.']}, {'end': 1493.987, 'start': 1343.882, 'title': 'Understanding tabulation in dynamic programming', 'summary': 'Explains the bottom-up approach of tabulation in dynamic programming, using a base case of 0 and calculating the maximum value of dp of i as the take case minus non-take case, while addressing edge cases and negative indices.', 'duration': 150.105, 'highlights': ['The chapter explains the bottom-up approach of tabulation in dynamic programming.', 'The maximum value of dp of i is calculated as the take case minus non-take case.', 'The base case of 0 is used in the tabulation process.', 'Addressing edge cases and negative indices is an integral part of the tabulation process.']}], 'duration': 264.714, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1229273.jpg', 'highlights': ['The importance of pre-stored values to optimize time complexity is emphasized, reducing the need for further recursion calls and increasing efficiency.', 'The process of converting memoization into tabulation is discussed, involving the declaration of a DP array of the same size and filling it with zeros, followed by handling base cases and index traversal for efficient computation.', 'The chapter explains the bottom-up approach of tabulation in dynamic programming.', 'Addressing edge cases and negative indices is an integral part of the tabulation process.', 'The maximum value of dp of i is calculated as the take case minus non-take case.', 'The base case of 0 is used in the tabulation process.']}, {'end': 1933.137, 'segs': [{'end': 1522.289, 'src': 'embed', 'start': 1494.387, 'weight': 1, 'content': [{'end': 1501.391, 'text': 'And if I ask you the time complexity now, big O of n, space complexity, just a big O of n, no auxiliary stack space.', 'start': 1494.387, 'duration': 7.004}, {'end': 1506.975, 'text': "That's the time complexity and the space complexity for this particular tabulation code.", 'start': 1502.072, 'duration': 4.903}, {'end': 1510.057, 'text': 'And I hope it was as simple as it could have been.', 'start': 1506.995, 'duration': 3.062}, {'end': 1512.798, 'text': "What's the next step that I generally do? Come on, guys.", 'start': 1510.637, 'duration': 2.161}, {'end': 1514.96, 'text': 'This is something which none of the creators does.', 'start': 1513.199, 'duration': 1.761}, {'end': 1522.289, 'text': 'kids space optimization no one does this Check it out.', 'start': 1515.779, 'duration': 6.51}], 'summary': 'Tabulation code has time complexity o(n) and space complexity o(n). unique space optimization is not commonly performed.', 'duration': 27.902, 'max_score': 1494.387, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1494387.jpg'}, {'end': 1566.296, 'src': 'embed', 'start': 1535.939, 'weight': 0, 'content': [{'end': 1542.003, 'text': 'But over here, you get everything including space optimization, which is the ultimate form of DP.', 'start': 1535.939, 'duration': 6.064}, {'end': 1545.045, 'text': "Like, if you don't do space optimization, you don't know DP.", 'start': 1542.263, 'duration': 2.782}, {'end': 1545.866, 'text': 'As simple as that.', 'start': 1545.245, 'duration': 0.621}, {'end': 1548.247, 'text': 'Then you are just keeping patterns.', 'start': 1546.326, 'duration': 1.921}, {'end': 1553.687, 'text': "If you're understanding how to do space optimization, you're actually understanding DP index.", 'start': 1549.244, 'duration': 4.443}, {'end': 1557.29, 'text': 'That last two states, and so on and so on.', 'start': 1553.967, 'duration': 3.323}, {'end': 1558.971, 'text': "So let's analyze over here.", 'start': 1557.65, 'duration': 1.321}, {'end': 1566.296, 'text': "In order to compute DP of I, what am I requiring? I'm requiring a DP of I minus one.", 'start': 1560.372, 'duration': 5.924}], 'summary': 'Understanding space optimization is crucial in dynamic programming (dp) to compute dp of i, requiring dp of i minus one.', 'duration': 30.357, 'max_score': 1535.939, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1535939.jpg'}], 'start': 1494.387, 'title': 'Space optimization in dynamic programming', 'summary': 'Explains achieving time complexity of o(n) and space complexity of o(1) in tabulation code, highlighting the importance of space optimization for comprehensive understanding of dynamic programming.', 'chapters': [{'end': 1933.137, 'start': 1494.387, 'title': 'Space optimization in dynamic programming', 'summary': 'Explains space optimization in dynamic programming, demonstrating how to achieve a time complexity of big o of n and a space complexity of big o of 1 in tabulation code, emphasizing the importance of understanding space optimization for a comprehensive grasp of dynamic programming.', 'duration': 438.75, 'highlights': ['Space optimization is the ultimate form of dynamic programming, essential for a comprehensive understanding of DP, as it reduces the space complexity to big O of 1, enabling the storage of only the last two required values for computation.', 'The tabulation code achieves a time complexity of big O of n and a space complexity of big O of 1, showcasing the efficiency of space optimization in dynamic programming.', 'The chapter emphasizes the significance of space optimization in dynamic programming, highlighting its inclusion as the ultimate form of DP and the requirement to understand it for a comprehensive grasp of DP.']}], 'duration': 438.75, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/GrMBfJNk_NY/pics/GrMBfJNk_NY1494387.jpg', 'highlights': ['Space optimization is the ultimate form of dynamic programming, reducing space complexity to O(1).', 'Tabulation code achieves time complexity of O(n) and space complexity of O(1).', 'Significance of space optimization in dynamic programming is emphasized.']}], 'highlights': ['The process of applying memoization to the dynamic programming solution is explained, highlighting the creation of an array for storing computed values and the significant reduction in time complexity to O(n).', 'The importance of pre-stored values to optimize time complexity is emphasized, reducing the need for further recursion calls and increasing efficiency.', 'The importance of understanding memorization, tabulation, and space optimization for mastering dynamic programming is emphasized.', 'The maximum sum of the subsequence can be achieved by picking up non-adjacent elements, illustrated with an example of achieving a maximum sum of 11 from the given array.', 'Space optimization is the ultimate form of dynamic programming, reducing space complexity to O(1).', 'The lecture focuses on solving the problem of finding the maximum sum of non-adjacent elements using a unique teaching approach.']}