JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

DPL5 Maximum Sum of Non-Adjacent Elements or House Robber 1-D

Given an array of ‘N’ positive integers, we need to return the maximum sum of the subsequence such that no two elements of the subsequence are adjacent elements in the array.

Note: A subsequence of an array is a list with elements of the array where some elements are deleted ( or not deleted at all) and the elements should be in the same order in the subsequence as in the array.

Now the first Things Comes in my mind is How can i find the all the Possible Subsecquance, Now her the Comes the Concepy of the Pick and Not Pick that we learned in the Recursion Playlist.

Recursice Approch

Steps to form the recursive solution
Step 1: Form the function in terms of indexes:

We are given an array which can be easily thought of in terms of indexes.

We can define our function f(ind) as : Maximum sum of the subsequence starting from index 0 to index ind.

We need to return f(n-1) as our final answer.

Step 2: Try all the choices to reach the goal.
Now here we used the Concept of the pick/non-pick technique to generate all subsequences. We also need to take care of the non-adjacent elements in this step.

If we pick an element then, pick = arr[ind] + f(ind-2). The reason we are doing f(ind-2) is because we have picked the current index element so we need to pick a non-adjacent element so we choose the index ‘ind-2’ instead of ‘ind-1’.

Next we need to ignore the current element in our subsequence. So nonPick= 0 + f(ind-1). As we don’t pick the current element, we can consider the adjacent element in the subsequence.

Step 3: Take the maximum of all the choices

Accoding to the Question we find the maximum subsequence total, we will return the maximum of two choices from step2.

Recursion Base Conditions
The base conditions for the recursive Solution

If ind=0, then we know to reach at index=0, we would have ignored the element at index = 1. Therefore, we can simply return the value of arr[ind] and consider it in the subsequence.

If ind < 0, this case can we cross the limit of the Index so Simply return 0.

Time & Space Complexity

Time Complexity: O(2 ^ N)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Now gere we see How Rewcursion Work Internally.

Steps to convert Recursive code to memoization solution:

Create a dp[n] array initialized to -1.

Whenever we want to find the answer of a particular value (say n), we first check whether the answer is already calculated using the dp array(i.e dp[n]!= -1 ). If yes, simply return the value from the dp array.

If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[n] to the solution we get.

Time & Space Complexity

Time Complexity: O(N)
Reason: The overlapping subproblems will return the answer in constant time O(1). Therefore the total number of new subproblems we solve is ‘n’. Hence total time complexity is O(N)..
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N)) and an array (again O(N)). Therefore total space complexity will be O(N) + O(N) ≈ O(N)

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

Steps to convert Recursive Solution to Tabulation one.

Declare a dp[] array of size n+1.

First, initialize the base condition values, i.e dp[0] as 0.

Set an iterative loop that traverses the array( from index 1 to n-1) and for every index calculate jumpOne and jumpTwo and set dp[i] = min(jumpOne, jumpTwo).

Time & Space Complexity

Time Complexity: O(N*K)
Reason: We are running two nested loops, where outer loops run from 1 to n-1 and the inner loop runs from 1 to K
Space Complexity: O(N)
Reason: We are using an external array of size ‘n’.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: ( i,i-1,i-2) for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

dp[i], dp[i-1], and dp[i-2]

we see that for any i, we do need only the last two values in the array. So no need to maintain a whole array for the ans

Each iteration’s currIndx and prev become the next iteration’s prev and prev2 respectively.

Therefore after calculating currIndx, if we update prev and prev2 according to the next step, we will always get the answer.

After the iterative loop has ended we can simply return prev as our answer.

Time & Space Complexity

Time Complexity: O(N)
Reason: We are running a simple iterative loop
Space Complexity: O(1)
Reason: We are not using any extra space.