## Brute Force Intuition ✊

The intuition is obvious; we will make all the possible cases and find the best possible answer. At every step, we have two options, i.e., to either select the element in our final sum or to not select the element in our final answer. If we didn't select the element, we could simply move to the next element, and if we select that particular element, then we will be shifted to the **current index + element's value**. After getting all the answers from all possible cases, we can finalize the answer by looking at whose value is maximum. Now let’s jump to the Dynamic programming solution.

## Approach

__Dynamic Programming__ can be used to tackle the problem. The approach would be to take a DP table that will keep the maximum score from that index to the end of the array.

**But how?** 🤔

After creating a DP table, we will also initialize a variable named ‘**MAX_SUM**’ which will store our final answer. Now we know one thing that value of **DP[N - 1] **would be equal to **ARR[N - 1] **because the maximum sum from the last index can be **ARR[N-1] **only.

Now we will start looping from** N - 2** till we reach the start of the array and check

```
If (i + ARR[i] < N)
DP[i] = DP[i] + DP[i + ARR[i]].
MAX_SUM = max(MAX_SUM, DP[i]).
```

Finally, we can return **MAX_SUM** as our answer.

These words will come into play by the following code.

## Code 🧑💻

```
#include <iostream>
#include <vector>
using namespace std;
// Function that will maximize the sum of elements 'ARR[i]' selected by jumping index by value 'i'.
int maximumSum(vector<int> &arr)
{
int n = arr.size();
// Declaring and initializing 'DP' array.
vector<int> dp(n + 1, 0);
dp[n - 1] = arr[n - 1];
// Maximum sum will be stored in 'MAX_SUM'.
int maxSum = 0;
// Iterating over the array.
int i = n - 2;
while (i >= 0)
{
dp[i] = arr[i];
if (arr[i] + i < n)
{
dp[i] += dp[arr[i] + i];
}
maxSum = max(dp[i], maxSum);
i--;
}
// Returning the answer.
return maxSum;
}
int main()
{
int n;
cin >> n;
vector<int> arr(n, 0);
// Taking input.
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
arr[i] = x;
}
cout << maximumSum(arr);
return 0;
}
```

### Input 📩

5

1 2 3 4 5

### Output 📤

7

### Time Complexity ⏳

**O(N)**, where ‘N’ is the size of the array.

As we are traversing over the array only once thus, the time complexity would be **O(N)**.

### Space Complexity

**O(N), **where ‘N’ is the array 'ARR's length.

As we have used an extra DP array of size ‘N,’ thus the overall space complexity is **O(N)**.

## Frequently Asked Questions

**What is Dynamic Programming?**

Dynamic programming is a problem-solving technique; dividing problems into sub-problems and saving the result for later use, that eliminates the need to recalculate the result. The optimal substructure property describes how subproblems are optimized to improve the overall solution.

**What is an array?**

An array data structure, or simply an array, is a data structure in computer science that consists of a element collection, each of which is identified by at least one array index/key. An array is stored in a way that the position of each component can be calculated using a mathematical formula from its index tuple.

**What distinguishes dynamic programming from memoization and recursion?**

Recursion is the process of repeatedly calling the same function. Memorization is a method of storing the answers to subproblems that have been solved. Dynamic programming is a recursive problem-solving process that involves keeping the solutions to previously solved subproblems.

**What are the cons of memoization or a top-down approach?**

Memoization or a top-down approach uses the recursion technique that occupies more memory in the call stack. The stack overflow condition will occur if the recursion is too deep. It occupies more memory which degrades the overall performance.

###
**Are there any other Data Structures and Algorithms content in Coding Ninjas Studio****?**

Coding Ninjas Studio allows you to practice coding and answer frequently asked interview questions. The more we practice, the more likely we will acquire a job at our dream company.

## Conclusion

We saw how we solved the problem maximize the sum of elements ARR[i] selected by jumping index by value i’ using Dynamic Programming. There are many other variations to this problem, but you don’t have to worry about them when your ninja friend is here. Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in pygame, Competitive Programming, JavaScript, 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 suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Check out the following problems -

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 Learning!