Dada una array arr[] , la tarea es calcular la suma máxima de elementos de la array de modo que, si se elige un i-ésimo elemento, entonces arr[i] se agrega a la suma y los saltos i se adelantan desde el índice actual .
Ejemplos :
Entrada: N = 5, arr[] = {7, 3, 1, 2, 3}
Salida: 7
Explicación:
- Toma el primer elemento 7 a nuestra puntuación, luego movemos el índice 7 hacia adelante y sale de la array, por lo que la respuesta final es 7.
- Comience desde el segundo elemento 3 y agréguelo al puntaje, luego muévase 3 índices hacia adelante y aterrice en el último índice de la array y agréguelo a nuestro puntaje, por lo que el puntaje final será 3+3=6.
- Comience desde el tercer elemento 1 y agregue a nuestro puntaje, luego avance 1 índice y agregue 2 a nuestro puntaje, por lo que el puntaje final es = 1 + 2 = 3.
- Comience desde el cuarto elemento 2 y agréguelo a la puntuación y avance 2 índices a medida que salimos de la array, la puntuación final es 2.
- Comience desde el quinto elemento 3 y agréguelo a nuestro puntaje y nuestro puntaje final será 3.
Entonces, de todos los casos, la puntuación máxima es 7.
Entrada: N = 2, arr[] = {3, 1}
Salida: 3
Enfoque : La tarea se puede resolver usando Programación Dinámica . Tome un contenedor dp que almacenará la puntuación máxima de ese índice en particular hasta el final de la array y, después de averiguar la puntuación máxima para todos los índices, imprima la puntuación máxima de ellos.
Siga los pasos a continuación para resolver el problema:
- Cree un contenedor Dp del mismo tamaño que la array y la variable ans .
- Ahora asigne dp[n-1] como arr[n-1] porque la suma máxima de ese índice es a[n-1] .
- Iterar el ciclo hacia atrás de n-2 a 0.
- Para cada índice, agregue arr[i] al dp y verifique
- si i+arr[i] es menor que el tamaño de la array
- en caso afirmativo, agregue dp[i+arr[i]] a dp[i].
- si i+arr[i] es menor que el tamaño de la array
- Itere la array dp y encuentre el máximo de dp y guárdelo en nuestra variable ans.
- Finalmente, imprima ans.
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 to find the maximum
// score from the given array.
void findMaximumScore(int arr[], int n)
{
// Initialize dp.
int dp[n + 1] = { 0 };
dp[n - 1] = arr[n - 1];
// Store the max sum
int ans = 0;
// Iterating backwards from n-2 to 0.
for (int i = n - 2; i >= 0; i--) {
dp[i] = arr[i];
int j = i + arr[i];
if (j < n) {
dp[i] += dp[j];
}
}
// Finding the maximum
// score present in the dp.
for (int i = 0; i < n; i++) {
ans = max(dp[i], ans);
}
cout << ans << endl;
}
// Driver Code
int main()
{
int n = 5;
int arr[] = { 7, 3, 1, 2, 3 };
findMaximumScore(arr, n);
return 0;
}
Java
// Java program for the above approach
public class GFG {
// Function to to find the maximum
// score from the given array.
static void findMaximumScore(int arr[], int n)
{
// Initialize dp.
int dp[] = new int[n + 1];
dp[n - 1] = arr[n - 1];
// Store the max sum
int ans = 0;
// Iterating backwards from n-2 to 0.
for (int i = n - 2; i >= 0; i--) {
dp[i] = arr[i];
int j = i + arr[i];
if (j < n) {
dp[i] += dp[j];
}
}
// Finding the maximum
// score present in the dp.
for (int i = 0; i < n; i++) {
ans = Math.max(dp[i], ans);
}
System.out.println(ans);
}
// Driver Code
public static void main (String[] args)
{
int n = 5;
int arr[] = { 7, 3, 1, 2, 3 };
findMaximumScore(arr, n);
}
}
// This code is contributed by AnkThon
Python3
# Python Program to implement # the above approach # Function to to find the maximum # score from the given array. def findMaximumScore(arr, n): # Initialize dp. dp = [0] * (n + 1) dp[n - 1] = arr[n - 1] # Store the max sum ans = 0 # Iterating backwards from n-2 to 0. for i in range(n-2, -1, -1): dp[i] = arr[i] j = i + arr[i] if (j < n): dp[i] += dp[j] # Finding the maximum # score present in the dp. for i in range(n): ans = max(dp[i], ans) print(ans) # Driver Code n = 5 arr = [7, 3, 1, 2, 3] findMaximumScore(arr, n) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
public class GFG {
// Function to to find the maximum
// score from the given array.
static void findMaximumScore(int []arr, int n)
{
// Initialize dp.
int []dp = new int[n + 1];
dp[n - 1] = arr[n - 1];
// Store the max sum
int ans = 0;
// Iterating backwards from n-2 to 0.
for (int i = n - 2; i >= 0; i--) {
dp[i] = arr[i];
int j = i + arr[i];
if (j < n) {
dp[i] += dp[j];
}
}
// Finding the maximum
// score present in the dp.
for (int i = 0; i < n; i++) {
ans = Math.Max(dp[i], ans);
}
Console.WriteLine(ans);
}
// Driver Code
public static void Main (string[] args)
{
int n = 5;
int []arr = { 7, 3, 1, 2, 3 };
findMaximumScore(arr, n);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to to find the maximum
// score from the given array.
function findMaximumScore(arr, n)
{
// Initialize dp.
let dp = new Array(n + 1).fill(0)
dp[n - 1] = arr[n - 1];
// Store the max sum
let ans = 0;
// Iterating backwards from n-2 to 0.
for (let i = n - 2; i >= 0; i--) {
dp[i] = arr[i];
let j = i + arr[i];
if (j < n) {
dp[i] += dp[j];
}
}
// Finding the maximum
// score present in the dp.
for (let i = 0; i < n; i++) {
ans = Math.max(dp[i], ans);
}
document.write(ans + '<br>');
}
// Driver Code
let n = 5;
let arr = [7, 3, 1, 2, 3];
findMaximumScore(arr, n);
// This code is contributed by Potta Lokesh
</script>
Producción
7
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por shrayansh95 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA