Maximizar la suma posible de una array por los movimientos dados

Dados tres enteros N, M y K y una array a[] que consta de N enteros, donde M y K denotan el número total de movimientos posibles y el número de movimientos posibles (desplazamiento por un índice) a la izquierda del elemento actual en una array respectivamente, la tarea es maximizar la suma posible atravesando la array utilizando todos los movimientos disponibles.

Ejemplos:

Entrada: N = 5, M = 4, K = 0, a[] = {1, 5, 4, 3, 2} Salida: 15 
Explicación : 
Dado 
que no es posible ningún movimiento hacia la izquierda, el único camino posible es un [0] -> a[1] -> a[2] -> a[3] -> a[4]. 
Por lo tanto, la suma calculada es 15.
Entrada: N = 5, M = 4, K = 1, a[]= {1, 5, 4, 3, 2} 
Salida: 19 
Explicación: 
La suma máxima se puede obtener en el ruta a[0] -> a[1] -> a[2] -> a[1] -> a[2] 
Por lo tanto, la suma máxima posible = 19

Enfoque: El problema anterior se puede resolver usando Programación Dinámica . Siga los pasos a continuación para resolver el problema:

• Inicialice una array dp[][] tal que dp[i][j] almacene la suma máxima posible hasta el i ^-ésimo índice usando j movimientos a la izquierda.
• Se puede observar que el movimiento hacia la izquierda es posible solo si i ≥ 1 y k > 0 y un movimiento hacia la derecha es posible si i < n – 1.
• Verifique las condiciones y actualice el máximo de las sumas posibles de los dos movimientos anteriores y guárdelo en dp[i][j] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int k = 1;
const int m = 4;
 
// Function to find the maximum sum possible
// by given moves from the array
int maxValue(int a[], int n, int pos,
             int moves, int left,
             int dp[][k + 1])
{
    // Checking for boundary
    if (moves == 0 || (pos > n - 1 || pos < 0))
        return 0;
 
    // If previously computed subproblem occurs
    if (dp[pos][left] != -1)
        return dp[pos][left];
 
    int value = 0;
 
    // If element can be moved left
    if (left > 0 && pos >= 1)
 
        // Calculate maximum possible sum
        // by moving left from current index
        value = max(value, a[pos] +
                    maxValue(a, n, pos - 1, moves - 1,
                             left - 1, dp));
 
    // If element can be moved right
    if (pos <= n - 1)
 
        // Calculate maximum possible sum
        // by moving right from current index
        // and update the maximum sum
        value = max(value, a[pos] +
                    maxValue(a, n, pos + 1,
                             moves - 1, left, dp));
 
    // Store the maximum sum
    return dp[pos][left] = value;
}
 
// Driver Code
int main()
{
    int n = 5;
    int a[] = { 1, 5, 4, 3, 2 };
 
    int dp[n + 1][k + 1];
    memset(dp, -1, sizeof(dp));
    cout << (a[0] + maxValue(a, n, 1, m, k, dp))
         << endl;
}
 
// This code is contributed by sapnasingh4991

// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to find the maximum sum possible
    // by given moves from the array
    public static int maxValue(int a[], int n, int pos,
                               int moves, int left,
                               int dp[][])
    {
        // Checking for boundary
        if (moves == 0 || (pos > n - 1 || pos < 0))
            return 0;
 
        // If previously computed subproblem occurs
        if (dp[pos][left] != -1)
            return dp[pos][left];
 
        int value = 0;
 
        // If element can be moved left
        if (left > 0 && pos >= 1)
 
            // Calculate maximum possible sum
            // by moving left from current index
            value = Math.max(
                value, a[pos] + maxValue(a, n, pos - 1,
                                         moves - 1, left - 1, dp));
 
        // If element can be moved right
        if (pos <= n - 1)
 
            // Calculate maximum possible sum
            // by moving right from current index
            // and update the maximum sum
            value = Math.max(
                value, a[pos]
                           + maxValue(a, n, pos + 1,
                                      moves - 1, left, dp));
 
        // Store the maximum sum
        return dp[pos][left] = value;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int n = 5;
        int a[] = { 1, 5, 4, 3, 2 };
        int k = 1;
        int m = 4;
 
        int dp[][] = new int[n + 1][k + 1];
        for (int i[] : dp)
            Arrays.fill(i, -1);
 
        System.out.println(
            (a[0] + maxValue(a, n, 1, m, k, dp)));
    }
}

# Python3 program to implement
# the above approach
 
# Function to find the maximum sum possible
# by given moves from the array
def maxValue(a, n, pos, moves, left, dp):
 
    # Checking for boundary
    if(moves == 0 or (pos > n - 1 or pos < 0)):
        return 0
 
    # If previously computed subproblem occurs
    if(dp[pos][left] != -1):
        return dp[pos][left]
 
    value = 0
 
    # If element can be moved left
    if(left > 0 and pos >= 1):
 
        # Calculate maximum possible sum
        # by moving left from current index
        value = max(value, a[pos] +
                    maxValue(a, n, pos - 1,
                                 moves - 1,
                                  left - 1, dp))
 
    # If element can be moved right
    if(pos <= n - 1):
 
        # Calculate maximum possible sum
        # by moving right from current index
        # and update the maximum sum
        value = max(value, a[pos] +
                    maxValue(a, n, pos + 1,
                                 moves - 1,
                                 left, dp))
                                  
    # Store the maximum sum
    dp[pos][left] = value
 
    return dp[pos][left]
 
# Driver Code
n = 5
a = [ 1, 5, 4, 3, 2 ]
k = 1
m = 4
 
dp = [[-1 for x in range(k + 1)]
          for y in range(n + 1)]
 
# Function call
print(a[0] + maxValue(a, n, 1, m, k, dp))
 
# This code is contributed by Shivam Singh

// C# Program to implement
// the above approach
using System;
class GFG
{
 
  // Function to find the maximum sum possible
  // by given moves from the array
  public static int maxValue(int []a, int n, int pos,
                             int moves, int left,
                             int [,]dp)
  {
    // Checking for boundary
    if (moves == 0 || (pos > n - 1 || pos < 0))
      return 0;
 
    // If previously computed subproblem occurs
    if (dp[pos, left] != -1)
      return dp[pos, left];
 
    int value = 0;
 
    // If element can be moved left
    if (left > 0 && pos >= 1)
 
      // Calculate maximum possible sum
      // by moving left from current index
      value = Math.Max(
      value, a[pos] + maxValue(a, n, pos - 1,
                               moves - 1,
                               left - 1, dp));
 
    // If element can be moved right
    if (pos <= n - 1)
 
      // Calculate maximum possible sum
      // by moving right from current index
      // and update the maximum sum
      value = Math.Max(
      value, a[pos] + maxValue(a, n, pos + 1,
                                 moves - 1,
                               left, dp));
 
    // Store the maximum sum
    return dp[pos, left] = value;
  }
 
  // Driver Code
  public static void Main(String []args)
  {
    int n = 5;
    int []a = { 1, 5, 4, 3, 2 };
    int k = 1;
    int m = 4;
 
    int [,]dp = new int[n + 1, k + 1];
    for(int i = 0; i <= n; i++)
      for(int j =0; j <= k; j++)
        dp[i, j] = -1;
 
    Console.WriteLine(
     (a[0] + maxValue(a, n, 1, m, k, dp)));
  }
}
 
// This code is contributed by Rajput-Ji

<script>
// JavaScript program for the
// above approach
  
   // Function to find the maximum sum possible
    // by given moves from the array
    function maxValue(a, n, pos, moves, left,
                               dp)
    {
        // Checking for boundary
        if (moves == 0 || (pos > n - 1 || pos < 0))
            return 0;
  
        // If previously computed subproblem occurs
        if (dp[pos][left] != -1)
            return dp[pos][left];
  
        let value = 0;
  
        // If element can be moved left
        if (left > 0 && pos >= 1)
  
            // Calculate maximum possible sum
            // by moving left from current index
            value = Math.max(
                value, a[pos] + maxValue(a, n, pos - 1,
                                         moves - 1, left - 1, dp));
  
        // If element can be moved right
        if (pos <= n - 1)
  
            // Calculate maximum possible sum
            // by moving right from current index
            // and update the maximum sum
            value = Math.max(
                value, a[pos]
                           + maxValue(a, n, pos + 1,
                                      moves - 1, left, dp));
  
        // Store the maximum sum
        return dp[pos][left] = value;
    }
 
// Driver Code
 
         let n = 5;
        let a = [ 1, 5, 4, 3, 2 ];
        let k = 1;
        let m = 4;
  
        let dp = new Array(n + 1);
        // Loop to create 2D array using 1D array
        for (var i = 0; i < dp.length; i++) {
            dp[i] = new Array(2);
        }
         
        for (var i = 0; i < dp.length; i++) {
            for (var j = 0; j < dp.length; j++) {
            dp[i][j] = -1;
        }
        }
  
        document.write(
            (a[0] + maxValue(a, n, 1, m, k, dp)));
 
</script>

19

Complejidad temporal: O(N * K) 
Espacio auxiliar: O(N * K)