Table of contents
1.
Introduction
2.
Understanding the Problem
2.1.
Explanation:
3.
Brute Force Intuition ✊
4.
Approach 
5.
Code 🧑‍💻
5.1.
Input 📩
5.2.
Output 📤
5.3.
Time Complexity ⏳
5.4.
Space Complexity
6.
Frequently Asked Questions
6.1.
What is Dynamic Programming?
6.2.
What is an array?
6.3.
What distinguishes dynamic programming from memoization and recursion?
6.4.
What are the cons of memoization or a top-down approach?
6.5.
Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Maximize the Sum of Elements ARR[i] Selected by Jumping Index by Value i

Author Adya Tiwari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

You can’t go to a technical interview without preparing the hot topic, i.e., Arrays. Interviews after the interview, we see questions of arrays being asked. Thus it’s important to master such a topic. So to help you, your Ninja is here, and today, we will see one such question, i.e., maximize the sum of elements ARR[i] selected by jumping index by value i. 

Now, let us start looking at the problem from a deeper perspective. 😉

Array CN

Understanding the Problem

We have been given an array ‘ARR’ of size ‘N.’ Our task is to find the maximum sum of elements from the array in such a way that if we pick an ith element, then ARR[i] will be added to the sum, and we will make the ‘ARR[i]’ several jumps from the current index till we cross the array. 

Things will become clearer from the following example

ARR = [1, 2, 3, 4, 5].

 

Now, in this example, our output will be

7.

Explanation:

We will try all possible positions.

✨Let’s first pick the number at the ‘0th’ index, then SUM = 1, and we will jump 1 index ahead. We will reach at index 1, so 2 is added in the sum (SUM += 2 = 3). Then, we will jump 2 indexes ahead and will reach index 3. So, 4 is added in the sum (SUM += 4 = 7). Now, if we jump 4 indexes ahead, we will cross out of the array. Thus, the final sum is 7.

✨Let’s now pick the number at index 1. So, SUM = 2.

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.

brute force gif

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;
}
You can also try this code with Online Python Compiler
Run Code

Input 📩

5

1 2 3 4 5

Output 📤

7

Time Complexity ⏳

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 pygameCompetitive ProgrammingJavaScriptSystem 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!

Live masterclass