Top-Down Approach (Memoization Method)
This approach is called the Top-Down approach because, in this type of approach, we start from the top dp state and go to the bottom state (base condition). We can optimize the above-stated approach by simply adding two new lines. We will memoize the above code to reduce the time complexity of the above approach.
Algorithm
- There would be only two changes in the above approach.
- First, we will create a dp array of size 1000001.
- After that, in the function solve(), we will add a condition that is the lifeline of this approach.
- The condition would be if (dp[n]!=-1) return dp[n]; this condition means that if the value of dp[n] is already computed, then we don't have to compute it again, and we can return from there.
- The next and last change would be in the end of the function, where we are returning the max value obtained from both the recursive calls. We will store the max value in the dp[n].
- In the end, we will return dp[n].
Code in C++
#include <bits/stdc++.h>
using namespace std;
// dp array
int dp[1000001];
// function to find the maximum sum
int solve(int a[], int n)
{
// base case
if (n < 0)
{
return 0;
}
if (dp[n] != -1)
{
return dp[n];
}
// if we pick the current element we move directly to index adjacent to the adjacent index
int pick = solve(a, n - 2) + a[n];
// if we donot pick the current element then we move to adjacent element
int notPick = solve(a, n - 1);
return dp[n] = max(pick, notPick);
}
int main()
{
int n = 5;
int a[n] = {4, 5, 3, 6, 1};
// Intializing the dp array with -1
memset(dp, -1, sizeof(dp));
cout << "The maximum sum is: " << solve(a, n - 1) << endl;
}
You can also try this code with Online C++ Compiler
Output
The maximum sum is: 11
Complexity Analysis
Time Complexity: O(N)
Since we are considering the valid subsequences only one time, the time complexity would be O(N).
Space Complexity: O(N)
Since we are using extra space in the form of the dp array, therefore the space complexity would be O(N).
Bottom-Up Approach (Tabulation Method)
The time complexity of this approach is the same as the approach stated above. It is just that this approach does not use extra stack space, which was used in the above approach when a recursive call was made. This approach is known as bottom-up because, in this approach, we start our transition from the bottom base state and reach our top most desired state.
Algorithm
- We will convert the above recursive approach to the iterative approach.
- First we will initialize the values of dp[0]=a[0], and dp[1]=max(a[1],a[0]).
- After that, we will run a for loop till n, and at each iteration, we will have two choices dp[i]=max(dp[i-2]+a[i],dp[i].
- In the end, we will return dp[n-1].
Code in C++
#include <bits/stdc++.h>
using namespace std;
// dp array
int dp[1000001];
// function to find the maximum sum
int solve(int a[], int n)
{
// intializing the first element of the dp array
dp[0] = a[0];
// intializing the second element of the dp array
dp[1] = max(a[1], a[0]);
for (int i = 2; i < n; i++)
{
// taking max out of the two choices
dp[i] = max(a[i] + dp[i - 2], dp[i - 1]);
}
return dp[n - 1];
}
int main()
{
int n = 5;
int a[n] = {5, 5, 10, 100, 1};
cout << "The maximum sum is: " << solve(a, n - 1) << endl;
}
You can also try this code with Online C++ Compiler
Output
The maximum sum is: 105
Complexity Analysis
Time Complexity: O(N)
Since we are using only one for loop till N, the time complexity would be O(N).
Space Complexity: O(N)
Since we are using extra space in the form of the dp array, therefore the space complexity would be O(N).
Space Optimized Approach
This approach is a continuation of the above-stated approach. In this approach, we will improve the space complexity of the above-stated code. The time complexity will remain the same, but the space complexity will be improved.
Algorithm
- In this approach, we will eliminate the dp array and use only variables.
- First, create a curr variable, initialize it with a[0], and create another variable named prev and initialize it with zero.
- Store the max value at every iteration in the for loop, excluding the current element in a variable named curr_new.
- After that assign the perform this curr=prev+a[i] and prev=curr_new.
- In the end return max(prev,curr).
Code in C++
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum sum
int solve(int a[], int n)
{
// initialzing the curr variable with a[0], and prev with 0
int curr = a[0], prev = 0;
for (int i = 1; i < n; i++)
{
// current max sum exluding the current element
int curr_new = max(curr, prev);
// current max sum including the current element
curr = prev + a[i];
prev = curr_new;
}
return max(curr, prev);
}
int main()
{
int n = 6;
int a[n] = {9, 11, 8, 3, 10, 22};
cout << "The maximum sum is: " << solve(a, n) << endl;
}
You can also try this code with Online C++ Compiler
Output
The maximum sum is: 39
Complexity Analysis
Time Complexity: O(N)
Since we are using only one for loop till N, the time complexity would be O(N).
Space Complexity: O(1)
Since we are not using any extra space, the space complexity would be O(1).
Frequently asked questions
What are the characteristics of dynamic programming?
Dynamic programming has the following characteristics:
- Optimal Substructures: A problem has an optimal substructure property if the overall optimal solution is determined by evaluating the optimal solutions of all subproblems.
-
Overlapping subproblems: When a larger problem is divided into smaller problems, the smaller problems are referred to as subproblems. Consider the following example of calculating fibonacci(4) number. Fibonacci(4) is obtained by adding fibonacci(3) and fibonacci(2), fibonacci(3) is calculated by adding fibonacci(2) and fibonacci(1), and fibonacci(2) is calculated by adding fibonacci(3) and fibonacci(1).
What distinguishes dynamic programming from memoization and recursion?
Recursion is the process of repeatedly calling the function itself. Memoization is a method of storing the answer to previously solved subproblems. Dynamic programming is a technique for solving recursions by retrieving answers to previously solved subproblems.
What factors should you consider while deciding between top-down and bottom-up approaches to the same problem?
When determining which algorithm to use, there are two factors to consider.
- Time Complexity: In general, both techniques have the same time complexity, but because for loops are less expensive than recursive function calls, bottom-up can be quicker in machine time.
- Space Complexity (without taking into account additional call stack space during top-down): Bottom-up and Top-down approaches need the construction of a table for all sub-solutions, but because bottom-up follows a topological order, the cost of auxiliary space can sometimes be minimized to the size of the problem's immediate dependencies. For example, fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) requires just the previous two computations to be stored.
Conclusion
In this article, we have discussed the problem of finding the maximum sum such that no two elements are adjacent. We have discussed four different approaches for this problem: the brute force approach(recursive approach), the top-down approach, the bottom-up approach, space-optimized approach. We have also discussed all the approaches' time and space complexities.
We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve the problem and try some new and different approaches to this problem.
You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.
Nevertheless, you may consider our paid courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
Happy Coding.
34+ registered 
