Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.1.1.
Constraints
1.2.
Some Examples
2.
Brute Force Approach (Recursive Method)
2.1.
Algorithm
2.2.
Code in C++
2.2.1.
Complexity Analysis 
3.
Top-Down Approach (Memoization Method) 
3.1.
Algorithm
3.2.
Code in C++
3.2.1.
Complexity Analysis
4.
Bottom-Up Approach (Tabulation Method)
4.1.
Algorithm
4.2.
Code in C++
4.2.1.
Complexity Analysis
5.
Space Optimized Approach
5.1.
Algorithm
5.2.
Code in C++
5.2.1.
Complexity Analysis
6.
Frequently asked questions
6.1.
What are the characteristics of dynamic programming?
6.2.
What distinguishes dynamic programming from memoization and recursion?
6.3.
What factors should you consider while deciding between top-down and bottom-up approaches to the same problem?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Maximum sum such that no two elements are adjacent

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Dynamic Programming is one of the most important topics needed for the preparation of placements. Many companies like Amazon, Microsoft, and Google ask questions about Dynamic Programming in the interviews. So an individual needs to have a clear understanding of this topic.

In this blog, we will discuss a famous and basic problem of Dynamic Programming. We will discuss four different approaches to solve this problem. We will start with the brute force approach (i.e., recursive approach), and we will discuss its memoized version also, and in the end, we will discuss the bottom-up approach.

Problem Statement

Ninjas has an array of size N. He gave that array to you. He said he wanted to find the maximum sum of elements of an array such that no two elements are adjacent. But, the problem is that he cannot find the sum himself he is busy with some other task. Can you help him find the maximum sum?

Constraints

1<=N<=10^6

1<=A[i]<=10^7

Before we deep dive into the solution to this problem, we should look at some examples that will help us understand the problem better. 

Some Examples

Input

N=7, arr[] = {10, 1, 2, 9, 5, 7, 11}

 

Output

sum = 30

 

Explanation

We will take the following elements of the array to compute the sum (10, 9, 11).

Input

N=5, arr[] = {1, 8, 2, 3, 5}

 

Output

sum = 13 

 

Input

N=3, arr[] = {2,5,2}

 

Output

sum = 5

Brute Force Approach (Recursive Method)

The brute force approach to solving this problem is recursive. We will try out all the possible subsequences fulfilling the criteria. We will calculate the sum of every subsequence and take the maximum sum out of all the subsequences.   

Algorithm

  1. To solve this problem, we will create a function called solve(), and it will take two arguments: the initial array and the size of the array.
  2. After naming the function, we will first enlist the base case of the recursive function.
  3. Now, we will have two choices: to pick the current element and the other not to pick the current element.
  4. Therefore we will make two recursive calls and return the maximum of the values returned by these recursive calls.
  5. In the end, we will print the value returned from the function.

Code in C++

#include <bits/stdc++.h>
using namespace std;

// function to find the maximum sum
int solve(int a[], int n)
{
    // base case
    if (n < 0)
    {
        return 0;
    }

    // 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 max(pick, notPick);
}
int main()
{
    int n = 6;
    int a[n] = {4, 5, 1, 3, 6, 9};
    cout << "The maximum sum is: " << solve(a, n - 1) << endl;
}

 

Output

The maximum sum is: 17

 

Complexity Analysis 

Time Complexity: O(2^N)

Since we are trying out all the subsequences of the array, the time complexity would be exponential, i.e., 2^N.

Space Complexity: O(1)

Since we are not using extra space to compute the maximum sum, the space complexity is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

  1. There would be only two changes in the above approach.
  2. First, we will create a dp array of size 1000001.
  3. After that, in the function solve(), we will add a condition that is the lifeline of this approach. 
  4. 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.
  5. 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].
  6. 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;
}

 

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

  1. We will convert the above recursive approach to the iterative approach.
  2. First we will initialize the values of dp[0]=a[0], and dp[1]=max(a[1],a[0]).
  3. 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].
  4. 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;
}

 

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

  1. In this approach, we will eliminate the dp array and use only variables.
  2. First, create a curr variable, initialize it with a[0], and create another variable named prev and initialize it with zero.
  3. Store the max value at every iteration in the for loop, excluding the current element in a variable named curr_new.
  4. After that assign the perform this curr=prev+a[i] and prev=curr_new.
  5. 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;
}

 

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 AlgorithmsCompetitive ProgrammingSystem 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 problemsinterview 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.

Previous article
Minimum Score Triangulation of Polygon
Next article
Maximize the Sum of Elements ARR[i] Selected by Jumping Index by Value i
Live masterclass