## 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

- 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.
- After naming the function, we will first enlist the base case of the recursive function.
- Now, we will have two choices: to pick the current element and the other not to pick the current element.
- Therefore we will make two recursive calls and return the maximum of the values returned by these recursive calls.
- 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).