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