Maximum score possible from an array with jumps of at most length K

0 0 14 minutes read

Given an array arr[] and an integer K, the 0^th index, the task is to collect the maximum score possible by performing the following operations:

Start from the 0^th 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 0^th index, perform the following operations for every i^th 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 index
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_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 Code
int 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 approach
import 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 approach
import sys
 
# Function to count the maximum
# score of an index
def 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 A
def 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 Code
if __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 approach
using 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 Code
static 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

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 code
int 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 approach
import 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 approach
 
function getScore(A, N, K) {
// Initialize dp array with values for the last element
let dp = new Array(N);
dp[N - 1] = A[N - 1];
// Traverse dp array from the second last index to the first
for (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 answer
return dp[0];
}
 
// Driver code
let A = [100, -30, -50, -15, -20, -30];
let K = 3;
let N = A.length;
 
// function call
console.log(getScore(A, N, K));

Output

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 0^th index, the score will be the value at the 0^th index.
- Now, for every i^th 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 i^th 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 Code
A = [-44, -17, -54, 79]
K = 2
N = 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

Time Complexity: O(N * log K)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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