Given an array arr[] and an integer K, the 0th index, the task is to collect the maximum score possible by performing the following operations:
- Start from the 0th index of the array.
- Reach the last index of the array by jumping at most K indices in each move.
- Add the value of every index reached after each jump.
- Initialize an array dp[] to store the previously computed results.
- Now, starting from the 0th index, perform the following operations for every ith index:
- If the current index is greater than or equal to the index of the last element, return the last element of the array.
- If the value for the current index is pre-calculated, then return the pre-calculated value.
- Otherwise, calculate maximum score that can be obtained by moving to all steps in the range i + 1 to i + K and store results for respective indices in dp[] array using the following recurrence relation:
dp[i] = max(dp[i + 1], dp[i + 2], dp[i + 3], ….., dp[i + K]) + A[i].
- Now, print dp[0] as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the maximum// score of an indexint maxScore(int i, int A[], int K, int N, int dp[]){ // Base Case if (i >= N - 1) return A[N - 1]; // If the value for the current // index is pre-calculated if (dp[i] != -1) return dp[i]; int score = INT_MIN; // Calculate maximum score // for all the steps in the // range from i + 1 to i + k for (int j = 1; j <= K; j++) { // Score for index (i + j) score = max(score, maxScore(i + j, A, K, N, dp)); } // Update dp[i] and return // the maximum value return dp[i] = score + A[i];}// Function to get maximum score// possible from the array A[]int getScore(int A[], int N, int K){ // Array to store memoization int dp[N]; // Initialize dp[] with -1 for (int i = 0; i < N; i++) dp[i] = -1; cout << maxScore(0, A, K, N, dp);}// Driver Codeint main(){ int A[] = { 100, -30, -50, -15, -20, -30 }; int K = 3; int N = sizeof(A) / sizeof(A[0]); getScore(A, N, K); return 0;} |
Java
// JAVA program for the above approachimport java.io.*;import java.math.*;import java.util.*;public class GFG { // Function to count the maximum // score of an index static int maxScore(int i, int A[], int K, int N, int dp[]) { // Base Case if (i >= N - 1) return A[N - 1]; // If the value for the current // index is pre-calculated if (dp[i] != -1) return dp[i]; int score = Integer.MIN_VALUE; // Calculate maximum score // for all the steps in the // range from i + 1 to i + k for (int j = 1; j <= K; j++) { // Score for index (i + j) score = Math.max(score, maxScore(i + j, A, K, N, dp)); } // Update dp[i] and return // the maximum value return dp[i] = score + A[i]; } // Function to get maximum score // possible from the array A[] static void getScore(int A[], int N, int K) { // Array to store memoization int dp[] = new int[N]; // Initialize dp[] with -1 for (int i = 0; i < N; i++) dp[i] = -1; System.out.println(maxScore(0, A, K, N, dp)); } // Driver Code public static void main(String args[]) { int A[] = { 100, -30, -50, -15, -20, -30 }; int K = 3; int N = A.length; getScore(A, N, K); }}// This code is contributed by jyoti369 |
Python3
# Python program for the above approachimport sys# Function to count the maximum# score of an indexdef maxScore(i, A, K, N, dp): # Base Case if (i >= N - 1): return A[N - 1]; # If the value for the current # index is pre-calculated if (dp[i] != -1): return dp[i]; score = 1-sys.maxsize; # Calculate maximum score # for all the steps in the # range from i + 1 to i + k for j in range(1, K + 1): # Score for index (i + j) score = max(score, maxScore(i + j, A, K, N, dp)); # Update dp[i] and return # the maximum value dp[i] = score + A[i]; return dp[i];# Function to get maximum score# possible from the array Adef getScore(A, N, K): # Array to store memoization dp = [0]*N; # Initialize dp with -1 for i in range(N): dp[i] = -1; print(maxScore(0, A, K, N, dp));# Driver Codeif __name__ == '__main__': A = [100, -30, -50, -15, -20, -30]; K = 3; N = len(A); getScore(A, N, K); # This code contributed by shikhasingrajput |
Javascript
<script>// javascript program of the above approach // Function to count the maximum // score of an index function maxScore(i, A, K, N, dp) { // Base Case if (i >= N - 1) return A[N - 1]; // If the value for the current // index is pre-calculated if (dp[i] != -1) return dp[i]; let score = -1000; // Calculate maximum score // for all the steps in the // range from i + 1 to i + k for (let j = 1; j <= K; j++) { // Score for index (i + j) score = Math.max(score, maxScore(i + j, A, K, N, dp)); } // Update dp[i] and return // the maximum value return dp[i] = score + A[i]; } // Function to get maximum score // possible from the array A[] function getScore(A, N, K) { // Array to store memoization let dp = new Array(N).fill(-1); document.write(maxScore(0, A, K, N, dp)); } // Driver Code let A = [ 100, -30, -50, -15, -20, -30 ]; let K = 3; let N = A.length; getScore(A, N, K);</script> |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the maximum // score of an index static int maxScore(int i, int []A, int K, int N, int []dp) { // Base Case if (i >= N - 1) return A[N - 1]; // If the value for the current // index is pre-calculated if (dp[i] != -1) return dp[i]; int score = int.MinValue; // Calculate maximum score // for all the steps in the // range from i + 1 to i + k for (int j = 1; j <= K; j++) { // Score for index (i + j) score = Math.Max(score, maxScore(i + j, A, K, N, dp)); } // Update dp[i] and return // the maximum value return dp[i] = score + A[i]; } // Function to get maximum score // possible from the array A[] static void getScore(int []A, int N, int K) { // Array to store memoization int []dp = new int[N]; // Initialize dp[] with -1 for (int i = 0; i < N; i++) dp[i] = -1; Console.WriteLine(maxScore(0, A, K, N, dp)); }// Driver Codestatic public void Main(){ int []A = { 100, -30, -50, -15, -20, -30 }; int K = 3; int N = A.Length; getScore(A, N, K);}}// This code is contributed by jana_sayantan. |
Output
55
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Another approach : DP tabulation ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Implementations Steps :
- Initialize a DP array of size N, where DP[i] represents the maximum score that can be obtained starting from position i.
- Initialize DP[N-1] with the value of the last element of the array A.
- Traverse the DP array from the second last index to the first.
- For each index i, consider all possible steps that can be taken from that position, i.e., 1 to K steps forward.
- For each step, calculate the maximum score that can be obtained by adding the score at the current position i to the maximum score that can be obtained from the destination position j.
- Update DP[i] with the maximum score obtained among all the possible steps.
- Return DP[0], which represents the maximum score that can be obtained starting from the first position.
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;int getScore(int A[], int N, int K) { // Initialize dp array with values for the last element int dp[N]; dp[N - 1] = A[N - 1]; // Traverse dp array from the second last index to the first for (int i = N - 2; i >= 0; i--) { // initial score int score = INT_MIN; for (int j = 1; j <= K && i + j < N; j++) { // Update the score with the maximum value // found among the possible steps score = max(score, dp[i + j]); } // Calculate the maximum score possible dp[i] = score + A[i]; } // return answer return dp[0];}// Driver codeint main() { int A[] = { 100, -30, -50, -15, -20, -30 }; int K = 3; int N = sizeof(A) / sizeof(A[0]); //function call cout << getScore(A, N, K); return 0;}// this code is contributed by bhardwajji |
Java
// Java program for above approachimport java.util.Arrays;public class Main { public static int getScore(int[] A, int N, int K) { // Initialize dp array with values for the last element int[] dp = new int[N]; dp[N - 1] = A[N - 1]; // Traverse dp array from the second last index to the first for (int i = N - 2; i >= 0; i--) { // initial score int score = Integer.MIN_VALUE; for (int j = 1; j <= K && i + j < N; j++) { // Update the score with the maximum value // found among the possible steps score = Math.max(score, dp[i + j]); } // Calculate the maximum score possible dp[i] = score + A[i]; } // return answer return dp[0]; } // Driver code public static void main(String[] args) { int[] A = { 100, -30, -50, -15, -20, -30 }; int K = 3; int N = A.length; // function call System.out.println(getScore(A, N, K)); }} |
Python3
class Main: @staticmethod def getScore(A, N, K): # Initialize dp array with values for the last element dp = [0] * N dp[N - 1] = A[N - 1] # Traverse dp array from the second last index to the first for i in range(N - 2, -1, -1): # initial score score = float('-inf') for j in range(1, K + 1): # Update the score with the maximum value # found among the possible steps if i + j < N: score = max(score, dp[i + j]) # Calculate the maximum score possible dp[i] = score + A[i] # return answer return dp[0]if __name__ == '__main__': A = [100, -30, -50, -15, -20, -30] K = 3 N = len(A) # function call print(Main.getScore(A, N, K)) |
C#
using System;public class Program { public static int GetScore(int[] A, int N, int K) { // Initialize dp array with values for the last element int[] dp = new int[N]; dp[N - 1] = A[N - 1]; // Traverse dp array from the second last index to the first for (int i = N - 2; i >= 0; i--) { // initial score int score = int.MinValue; for (int j = 1; j <= K && i + j < N; j++) { // Update the score with the maximum value // found among the possible steps score = Math.Max(score, dp[i + j]); } // Calculate the maximum score possible dp[i] = score + A[i]; } // return answer return dp[0]; } // Driver code public static void Main() { int[] A = { 100, -30, -50, -15, -20, -30 }; int K = 3; int N = A.Length; // function call Console.WriteLine(GetScore(A, N, K)); }} |
Javascript
// JavaScript program for above approachfunction getScore(A, N, K) {// Initialize dp array with values for the last elementlet dp = new Array(N);dp[N - 1] = A[N - 1];// Traverse dp array from the second last index to the firstfor (let i = N - 2; i >= 0; i--) { // initial score let score = -Infinity; for (let j = 1; j <= K && i + j < N; j++) { // Update the score with the maximum value // found among the possible steps score = Math.max(score, dp[i + j]); } // Calculate the maximum score possible dp[i] = score + A[i];}// return answerreturn dp[0];}// Driver codelet A = [100, -30, -50, -15, -20, -30];let K = 3;let N = A.length;// function callconsole.log(getScore(A, N, K)); |
Output
55
Time Complexity: O(N * K), where N is the size of the array and K is the input variable
Auxiliary Space: O(N)
Efficient Approach: Follow the steps below to solve the problem
- Initialize a Max Heap to store the result of previous K indices.
- Now, traverse the array A[] to calculate the maximum score for all indices.
- For 0th index, the score will be the value at the 0th index.
- Now, for every ith index in the range [1, N – 1].
- Firstly, remove maximum scores from the Max Heap for indices less than i – K.
- Now calculate the maximum score for ith index.
Maximum score = A[i] + score at the top of the Max Heap. - Now insert the maximum score into the max heap with its index.
- Return the maximum score obtained.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure to sort a priority queue on // the basis of first element of the pair struct mycomp { bool operator()(pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; } }; // Function to calculate maximum // score possible from the array A[] int maxScore(int A[], int K, int N) { // Stores the score of previous k indices priority_queue<pair<int, int>, vector<pair<int, int> >, mycomp> maxheap; // Stores the maximum // score for current index int maxScore = 0; // Maximum score at first index maxheap.push({ A[0], 0 }); // Traverse the array to calculate // maximum score for all indices for (int i = 1; i < N; i++) { // Remove maximum scores for // indices less than i - K while (maxheap.top().second < (i - K)) { maxheap.pop(); } // Calculate maximum score for current index maxScore = A[i] + maxheap.top().first; // Push maximum score of // current index along // with index in maxheap maxheap.push({ maxScore, i }); } // Return the maximum score return maxScore; } // Driver Code int main() { int A[] = { -44, -17, -54, 79 }; int K = 2; int N = sizeof(A) / sizeof(A[0]); // Function call to calculate // maximum score from the array A[] cout << maxScore(A, K, N); return 0; } |
Java
// Java code for the above approach:import java.util.*;public class Main { static class IntPair { int first; int second; IntPair(int x, int y) { this.first = x; this.second = y; } } static class HeapComparator implements Comparator<IntPair> { public int compare(IntPair p1, IntPair p2) { if (p1.first < p2.first) return 1; else if (p1.first > p2.first) return -1; return 0; } } // Function to calculate maximum // score possible from the array A[] static int maxScore(int A[], int K, int N) { // Stores the score of previous k indices PriorityQueue<IntPair> maxheap = new PriorityQueue<IntPair>( new HeapComparator()); // Stores the maximum // score for current index int maxScore = 0; // Maximum score at first index maxheap.add(new IntPair(A[0], 0)); // Traverse the array to calculate // maximum score for all indices for (int i = 1; i < N; i++) { // Remove maximum scores for // indices less than i - K while (maxheap.peek().second < (i - K)) { maxheap.remove(); } // Calculate maximum score for current index maxScore = A[i] + maxheap.peek().first; // Push maximum score of // current index along // with index in maxheap maxheap.add(new IntPair(maxScore, i)); } // Return the maximum score return maxScore; } // Driver Code public static void main(String args[]) { int A[] = { -44, -17, -54, 79 }; int K = 2; int N = A.length; // Function call to calculate // maximum score from the array A[] System.out.println(maxScore(A, K, N)); }}// This code has been contributed by Sachin Sahara// (sachin801) |
Python3
# Python program for the above approach# Function to calculate maximum# score possible from the array A[]def maxScore(A, K, N): # Stores the score of previous k indices maxheap = [] # Stores the maximum # score for current index maxScore = 0 # Maximum score at first index maxheap.append([A[0], 0]) # Traverse the array to calculate # maximum score for all indices for i in range(1, N): # Remove maximum scores for # indices less than i - K while(maxheap[len(maxheap) - 1][1] < (i - K)): maxheap.pop() # Calculate maximum score for current index maxScore = A[i] + maxheap[len(maxheap) - 1][0] # Push maximum score of # current index along # with index in maxheap maxheap.append([maxScore, i]) maxheap.sort() # Return the maximum score return maxScore# Driver CodeA = [-44, -17, -54, 79]K = 2N = len(A)# Function call to calculate# maximum score from the array A[]print(maxScore(A, K, N))# This code is contributed by Pushpesh Raj. |
Javascript
<script>// Javascript program for the above approach // Function to calculate maximum // score possible from the array A[] function maxScore(A, K, N) { // Stores the score of previous k indices var maxheap = []; // Stores the maximum // score for current index var maxScore = 0; // Maximum score at first index maxheap.push([A[0], 0]); // Traverse the array to calculate // maximum score for all indices for (var i = 1; i < N; i++) { // Remove maximum scores for // indices less than i - K while (maxheap[maxheap.length-1][1] < (i - K)) { maxheap.pop(); } // Calculate maximum score for current index maxScore = A[i] + maxheap[maxheap.length-1][0]; // Push maximum score of // current index along // with index in maxheap maxheap.push([maxScore, i]); maxheap.sort(); } // Return the maximum score return maxScore; } // Driver Code var A = [-44, -17, -54, 79]; var K = 2; var N = A.length; // Function call to calculate // maximum score from the array A[] document.write(maxScore(A, K, N)); // This code is contributed by noob2000.</script> |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function to calculate maximum // score possible from the array A[] static int maxScore(int[] A, int K, int N) { // Stores the score of previous k indices List<Tuple<int, int>> maxheap = new List<Tuple<int, int>> (); // Stores the maximum // score for current index int maxScore = 0; // Maximum score at first index maxheap.Add(Tuple.Create(A[0], 0)); // Traverse the array to calculate // maximum score for all indices for (int i = 1; i < N; i++) { // Remove maximum scores for // indices less than i - K while (maxheap[0].Item2 < (i - K)) { maxheap.RemoveAt(0); } // Calculate maximum score for current index maxScore = A[i] + maxheap[0].Item1; // Add maximum score of // current index along // with index in maxheap maxheap.Add(Tuple.Create(maxScore, i )); maxheap.Sort(); maxheap.Reverse(); } // Return the maximum score return maxScore; } // Driver Code public static void Main(string[] args) { int[] A = { -44, -17, -54, 79 }; int K = 2; int N = A.Length; // Function call to calculate // maximum score from the array A[] Console.WriteLine(maxScore(A, K, N)); }}// This code is contributed by phasing17. |
Output
18
Time Complexity: O(N * log K)
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!
