Dada una array arr[] y un entero K , el índice 0 , la tarea es recopilar la máxima puntuación posible realizando las siguientes operaciones:
- Comience desde el índice 0 de la array.
- Alcanza el último índice de la array saltando como máximo los índices K en cada movimiento.
- Agregue el valor de cada índice alcanzado después de cada salto.
- Inicialice una array dp[] para almacenar los resultados calculados previamente.
- Ahora, a partir del índice 0 , realice las siguientes operaciones para cada índice i :
- Si el índice actual es mayor o igual que el índice del último elemento, devuelve el último elemento de la array.
- Si el valor del índice actual se calculó previamente, devuelva el valor calculado previamente.
- De lo contrario, calcule la puntuación máxima que se puede obtener moviéndose a todos los pasos en el rango i + 1 a i + K y almacene los resultados para los índices respectivos en la array dp[] usando la siguiente relación de recurrencia:
dp[i] = max(dp[i + 1], dp[i + 2], dp[i + 3], ….., dp[i + K]) + A[i].
- Ahora, imprima dp[0] como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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
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.
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>
Producción
55
Complejidad de tiempo: O(N * K)
Espacio Auxiliar: O(N * K)
Enfoque eficiente: siga los pasos a continuación para resolver el problema
- Inicialice un Max Heap para almacenar el resultado de los índices K anteriores.
- Ahora, recorra la array A[] para calcular la puntuación máxima para todos los índices.
- Para el índice 0 , la puntuación será el valor en el índice 0 .
- Ahora, para cada i -ésimo índice en el rango [1, N – 1] .
- En primer lugar, elimine las puntuaciones máximas de Max Heap para índices inferiores a i – K.
- Ahora calcule la puntuación máxima para el i -ésimo índice.
Puntuación máxima = A[i] + puntuación en la parte superior de Max Heap. - Ahora inserte la puntuación máxima en el montón máximo con su índice.
- Devuelve la puntuación máxima obtenida.
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)
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>
Producción
18
Complejidad de tiempo: O(N * log K)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por divyagarg2601 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA