Given an array arr[] consisting of N positive integers and an integer K, the task is to find the maximum sum of array elements possible by jumps of (i + K*arr[i]) (< N) length from any ith index of the array.
Examples:
Input: arr[] = {1, 2, 1, 4}, K = 2
Output: 4
Explanation:
Starting index i = 0, the traversal of indices of array is {0, 2}
Hence, the answer is 4.Input: arr[] = {2, 1, 3, 1, 2}, K = 3
Output: 3
Naive Approach: The simplest approach is to traverse the given array for each possible starting index over the range [0, N – 1] and find the maximum of all the sum obtained by taking the jump of (i + K*arr[i]) from each possible index i. After all the traversal print the maximum sum obtained.
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;int max_sum(vector<int>& arr, int K) { int n = arr.size(); // Initialize the maximum sum to negative infinity int max_sum = INT_MIN; // Loop over each index in the array for (int i = 0; i < n; i++) { // current sum int cur_sum = 0; // Set the starting index of the jump to i int j = i; // Loop over each index reachable by jumps while (j < n) { cur_sum += arr[j]; // Calculate the index of the next jump j = j + i + K*arr[j]; } // Update the maximum sum if the current sum is greater max_sum = max(max_sum, cur_sum); } return max_sum; // Return the maximum sum}// Driver Codeint main() { vector<int> arr = {2, 1, 3, 1, 2}; int K = 3; cout << max_sum(arr, K) << endl; return 0;}// this code is contributed by bhardwajji |
C#
using System;public class Program { public static int MaxSum(int[] arr, int K) { int n = arr.Length; // Initialize the maximum sum to negative infinity int max_sum = int.MinValue; // Loop over each index in the array for (int i = 0; i < n; i++) { // current sum int cur_sum = 0; // Set the starting index of the jump to i int j = i; // Loop over each index reachable by jumps while (j < n) { cur_sum += arr[j]; // Calculate the index of the next jump j = j + i + K * arr[j]; } // Update the maximum sum if the current sum is // greater max_sum = Math.Max(max_sum, cur_sum); } return max_sum; // Return the maximum sum } // Driver Code public static void Main() { int[] arr = { 2, 1, 3, 1, 2 }; int K = 3; Console.WriteLine(MaxSum(arr, K)); }}// This code is contributed by sarojmcy2e |
Python
import sysdef max_sum(arr, K): n = len(arr) max_sum = -sys.maxsize - 1 # Initialize the maximum sum to negative infinity for i in range(n): # Loop over each index in the array cur_sum = 0 # current sum j = i # Set the starting index of the jump to i while j < n: # Loop over each index reachable by jumps cur_sum += arr[j] j = j + i + K*arr[j] # Calculate the index of the next jump max_sum = max(max_sum, cur_sum) # Update the maximum sum if the current sum is greater return max_sum # Return the maximum sum# Driver Codeif __name__ == "__main__": arr = [2, 1, 3, 1, 2] K = 3 print(max_sum(arr, K)) |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static int maxsum(int[] arr, int K) { int n = arr.length; // Initialize the maximum sum to negative infinity int max_sum = Integer.MIN_VALUE; // Loop over each index in the array for (int i = 0; i < n; i++) { // current sum int cur_sum = 0; // Set the starting index of the jump to i int j = i; // Loop over each index reachable by jumps while (j < n) { cur_sum += arr[j]; // Calculate the index of the next jump j = j + i + K * arr[j]; } // Update the maximum sum if the current sum is // greater max_sum = Math.max(max_sum, cur_sum); } return max_sum; // Return the maximum sum } // Driver Code public static void main(String[] args) { int[] arr = { 2, 1, 3, 1, 2 }; int K = 3; System.out.print(maxsum(arr, K)); }}// This code is contributed by shivanisingh.ss2110 |
Javascript
// Javascript program for above approach function max_sum(arr, K) { let n = arr.length; // Initialize the maximum sum to negative infinity let max_sum = Number.MIN_VALUE; // Loop over each index in the array for (let i = 0; i < n; i++) { // current sum let cur_sum = 0; // Set the starting index of the jump to i let j = i; // Loop over each index reachable by jumps while (j < n) { cur_sum += arr[j]; // Calculate the index of the next jump j = j + i + K * arr[j]; } // Update the maximum sum if the current sum is // greater max_sum = Math.max(max_sum, cur_sum); } return max_sum; // Return the maximum sum } // Driver Code let arr = { 2, 1, 3, 1, 2 }; let K = 3; console.log(maxsum(arr, K)); // This code is contributed by shivanisingh.ss2110 |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Dynamic Programming. The idea is to use an auxiliary array dp[] such that dp[i] stores the sum that can be obtained by choosing i as the starting index by using the following recurrence relation:
dp[i] = dp[i + K*arr[i]] + arr[i]
Follow the steps below to solve the problem:
- Initialize an auxiliary array dp[] of size N with {0}.
- Iterate over the range [N – 1, 0] using the variable i and perform the following steps:
- If the value of (i + K*arr[i] ≥ N), then update the value of dp[i] as arr[i].
- Otherwise, update the value of dp[i] as dp[i + K*arr[i]] + arr[i].
- After completing the above steps, print the maximum value in the array dp[] as the resultant maximum sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum// possible by jumps of length// i + K*arr[i] from any i-th indexvoid maxSum(int arr[], int N, int K){ // Initialize an array dp[] int dp[N + 2] = { 0 }; // Stores the maximum sum int maxval = 0; // Iterate over the range [N-1, 0] for (int i = N - 1; i >= 0; i--) { // If length of the jump exceeds N if ((i + K * arr[i]) >= N) { // Set dp[i] as arr[i] dp[i] = arr[i]; } // Otherwise, update dp[i] as // sum of dp[i + K * arr[i]] and arr[i] else { dp[i] = dp[i + K * arr[i]] + arr[i]; } // Update the overall maximum sum maxval = max(maxval, dp[i]); } // Print the answer cout << maxval;}// Driver Codeint main(){ int arr[] = { 2, 1, 3, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; maxSum(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum sum// possible by jumps of length// i + K*arr[i] from any i-th indexstatic void maxSum(int arr[], int N, int K){ // Initialize an array dp[] int[] dp = new int[N + 2]; Arrays.fill(dp, 0); // Stores the maximum sum int maxval = 0; // Iterate over the range [N-1, 0] for (int i = N - 1; i >= 0; i--) { // If length of the jump exceeds N if ((i + K * arr[i]) >= N) { // Set dp[i] as arr[i] dp[i] = arr[i]; } // Otherwise, update dp[i] as // sum of dp[i + K * arr[i]] and arr[i] else { dp[i] = dp[i + K * arr[i]] + arr[i]; } // Update the overall maximum sum maxval = Math.max(maxval, dp[i]); } // Print the answer System.out.print(maxval);}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 1, 3, 1, 2 }; int N = arr.length; int K = 3; maxSum(arr, N, K);}}// This code is contributed by code_hunt. |
Python3
# Python 3 program for the above approach# Function to find the maximum sum# possible by jumps of length# i + K*arr[i] from any i-th indexdef maxSum(arr, N, K): # Initialize an array dp[] dp = [0 for i in range(N+2)] # Stores the maximum sum maxval = 0 # Iterate over the range [N-1, 0] i = N - 1 while(i >= 0): # If length of the jump exceeds N if ((i + K * arr[i]) >= N): # Set dp[i] as arr[i] dp[i] = arr[i] # Otherwise, update dp[i] as # sum of dp[i + K * arr[i]] and arr[i] else: dp[i] = dp[i + K * arr[i]] + arr[i] # Update the overall maximum sum maxval = max(maxval, dp[i]) i -= 1 # Print the answer print(maxval)# Driver Codeif __name__ == '__main__': arr = [2, 1, 3, 1, 2] N = len(arr) K = 3 maxSum(arr, N, K) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG{// Function to find the maximum sum// possible by jumps of length// i + K*arr[i] from any i-th indexstatic void maxSum(int[] arr, int N, int K){ // Initialize an array dp[] int[] dp = new int[N + 2]; for(int i = 0; i< N+2; i++) { dp[i] = 0; } // Stores the maximum sum int maxval = 0; // Iterate over the range [N-1, 0] for (int i = N - 1; i >= 0; i--) { // If length of the jump exceeds N if ((i + K * arr[i]) >= N) { // Set dp[i] as arr[i] dp[i] = arr[i]; } // Otherwise, update dp[i] as // sum of dp[i + K * arr[i]] and arr[i] else { dp[i] = dp[i + K * arr[i]] + arr[i]; } // Update the overall maximum sum maxval = Math.Max(maxval, dp[i]); } // Print the answer Console.WriteLine(maxval);}// Driver Codestatic public void Main(){ int[] arr = { 2, 1, 3, 1, 2 }; int N = arr.Length; int K = 3; maxSum(arr, N, K);}}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum sum// possible by jumps of length// i + K*arr[i] from any i-th indexfunction maxSum(arr, N, K){ // Initialize an array dp[] let dp = []; for(let i = 0; i < N + 2; i++) { dp[i] = 0; } // Stores the maximum sum let maxval = 0; // Iterate over the range [N-1, 0] for (let i = N - 1; i >= 0; i--) { // If length of the jump exceeds N if ((i + K * arr[i]) >= N) { // Set dp[i] as arr[i] dp[i] = arr[i]; } // Otherwise, update dp[i] as // sum of dp[i + K * arr[i]] and arr[i] else { dp[i] = dp[i + K * arr[i]] + arr[i]; } // Update the overall maximum sum maxval = Math.max(maxval, dp[i]); } // Print the answer document.write(maxval);}// Driver Code let arr = [ 2, 1, 3, 1, 2 ]; let N = arr.length; let K = 3; maxSum(arr, N, K);</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
