Maximizar la suma de valores en el total de K pasos a partir de la posición M

Dada una array ordenada arr[] que contiene N pares [A, B] , donde A es la posición en el eje X y B es el valor en esa posición. Todas las posiciones son distintas. La array se ordena en orden creciente de posición. 
Dados dos enteros M y K . La tarea es maximizar la suma de valores que se pueden visitar comenzando desde la posición M y tomando K pasos totales donde:

• Uno puede moverse a la derecha o a la izquierda en 1 posición (de x a x+1 o x-1 ) dando 1 paso.
• El valor de cualquier posición se puede agregar a la suma final solo una vez.
• No hay movimiento a lo largo del eje Y.

Ejemplos:

Entrada: arr[][] = {{2, 8}, {6, 3}, {8, 6}}, M = 5, K = 4 Salida: 9 Explicación: La forma óptima es: Mover a
la derecha
a  la
posición 6 y sumamos 3. Movimiento 1 posición. 
Mover a la derecha a la posición 8 y sumar 6. Movimiento 2 posición.
Movimiento total 3 pasos y suma = 3 + 6 = 9.

Entrada: arr[][] = {{1, 7}, {3, 6}, {4, 5}, {6, 5}}, M = 3, K = 4 Salida: 18 Explicación:
La forma
óptima de el movimiento es:
Añadir valor en la posición 3 para responder.
Muévase hacia la derecha hasta la posición 4 y sume 5.
Muévase hacia la izquierda hasta la posición 1 y sume 7.
Suma total = 6 + 5 + 7 = 18.
Tenga en cuenta que la posición 3 se puede visitar dos veces, pero el valor se agrega solo una vez.

Entrada: arr[][] = {{0, 3}, {6, 4}, {8, 5}}, M = 3, K = 2 Salida: 0
Explicación :
El movimiento puede ser la mayoría de K = 2 posiciones y no puede llegar a cualquier posición con puntos.

Enfoque: El enfoque se basa en el concepto de suma de prefijos . El rango que se puede cubrir de pie en cualquier posición que deba determinarse en ese momento, los puntos totales se pueden calcular a partir de la array de suma de prefijos. Siga los pasos a continuación:

• Encuentre la suma de prefijos para la posición máxima posible. Después de eso, realiza dos bucles.
• El primer bucle será cuando se considere viajar primero a la derecha y luego a la izquierda.
• El segundo bucle se producirá cuando se mueva primero hacia la izquierda y luego hacia la derecha.
• El número máximo de Semillas cubiertas en todos los rangos factibles es la respuesta final.

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate maximum points
// that can be collected
int maxTotalPoints(vector<vector<int> >& arr,
                   int M, int K)
{
    int MX = 2e5 + 2;
    int i, l, r, ans = 0;
     
    // Incremented positions by one
    // to make calculations easier.
    M++;
    vector<int> prefix_sum(MX);
    for (auto& it : arr)
        prefix_sum[it[0] + 1] = it[1];
    for (i = 1; i < MX; i++)
        prefix_sum[i] += prefix_sum[i - 1];
 
    for (r = M; r < MX && r <= M + K; r++) {
        l = min(M, M - (K - 2 * (r - M)));
        l = max(1, l);
        ans = max(ans, prefix_sum[r] -
                  prefix_sum[l - 1]);
    }
 
    for (l = M; l > 0 && l >= M - K; l--) {
        r = max(M, M + (K - 2 * (M - l)));
        r = min(MX - 1, r);
        ans = max(ans, prefix_sum[r] -
                  prefix_sum[l - 1]);
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<vector<int>> arr{{2, 8}, {6, 3}, {8, 6}};
    int M = 5;
    int K = 4;
    cout<<maxTotalPoints(arr, M, K);
    return 0;
}

// Java code to implement above approach
import java.util.*;
class GFG
{
 
  // Function to calculate maximum points
  // that can be collected
  static int maxTotalPoints(int[][] arr,
                            int M, int K)
  {
    int MX = (int) (2e5 + 2);
    int i, l, r, ans = 0;
 
    // Incremented positions by one
    // to make calculations easier.
    M++;
    int []prefix_sum = new int[MX];
    for (int []it : arr)
      prefix_sum[it[0] + 1] = it[1];
    for (i = 1; i < MX; i++)
      prefix_sum[i] += prefix_sum[i - 1];
 
    for (r = M; r < MX && r <= M + K; r++) {
      l = Math.min(M, M - (K - 2 * (r - M)));
      l = Math.max(1, l);
      ans = Math.max(ans, prefix_sum[r] -
                     prefix_sum[l - 1]);
    }
 
    for (l = M; l > 0 && l >= M - K; l--) {
      r = Math.max(M, M + (K - 2 * (M - l)));
      r = Math.min(MX - 1, r);
      ans = Math.max(ans, prefix_sum[r] -
                     prefix_sum[l - 1]);
    }
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int [][]arr = {{2, 8}, {6, 3}, {8, 6}};
    int M = 5;
    int K = 4;
    System.out.print(maxTotalPoints(arr, M, K));
  }
}
 
// This code is contributed by 29AjayKumar

# Python code to implement above approach
 
# Function to calculate maximum points
# that can be collected
def maxTotalPoints(arr, M, K):
    MX = (int)(2e5 + 2);
    i, l, r, ans = 0, 0, 0, 0;
 
    # Incremented positions by one
    # to make calculations easier.
    M += 1;
    prefix_sum = [0 for i in range(MX)];
    for it in arr:
        prefix_sum[it[0] + 1] = it[1];
    for i in range(MX):
        prefix_sum[i] += prefix_sum[i - 1];
 
    for r in range(M, (M + K + 1) and ( r < MX and r <= M + K)):
        l = min(M, M - (K - 2 * (r - M)));
        l = max(1, l);
        ans = max(ans, prefix_sum[r] - prefix_sum[l - 1]);
 
    for l in range(M, (M - K - 1) and l > 0, -1):
        r = max(M, M + (K - 2 * (M - l)));
        r = min(MX - 1, r);
        ans = max(ans, prefix_sum[r] - prefix_sum[l - 1]);
 
    return ans;
 
# Driver code
if __name__ == '__main__':
    arr = [[2, 8], [6, 3], [8, 6]];
    M = 5;
    K = 4;
    print(maxTotalPoints(arr, M, K));
 
    # This code is contributed by 29AjayKumar

// C# code to implement above approach
using System;
class GFG
{
 
  // Function to calculate maximum points
  // that can be collected
  static int maxTotalPoints(int[,] arr,
                            int M, int K)
  {
    int MX = (int) (2e5 + 2);
    int i, l, r, ans = 0;
 
    // Incremented positions by one
    // to make calculations easier.
    M++;
    int []prefix_sum = new int[MX];
     
    for (int it = 0; it < arr.GetLength(0); it++) {
        prefix_sum[arr[it, 0] + 1] = arr[it, 1];
    }
     
    for (i = 1; i < MX; i++)
      prefix_sum[i] += prefix_sum[i - 1];
 
    for (r = M; r < MX && r <= M + K; r++) {
      l = Math.Min(M, M - (K - 2 * (r - M)));
      l = Math.Max(1, l);
      ans = Math.Max(ans, prefix_sum[r] -
                     prefix_sum[l - 1]);
    }
 
    for (l = M; l > 0 && l >= M - K; l--) {
      r = Math.Max(M, M + (K - 2 * (M - l)));
      r = Math.Min(MX - 1, r);
      ans = Math.Max(ans, prefix_sum[r] -
                     prefix_sum[l - 1]);
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int [,]arr = {{2, 8}, {6, 3}, {8, 6}};
    int M = 5;
    int K = 4;
    Console.Write(maxTotalPoints(arr, M, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to calculate maximum points
       // that can be collected
       function maxTotalPoints(arr, M, K)
       {
           let MX = 2e5 + 2;
           let i, l, r, ans = 0;
 
           // Incremented positions by one
           // to make calculations easier.
           M++;
           let prefix_sum = new Array(MX).fill(0);
           for (let it of arr)
               prefix_sum[it[0] + 1] = it[1];
           for (i = 1; i < MX; i++)
               prefix_sum[i] += prefix_sum[i - 1];
 
           for (r = M; r < MX && r <= M + K; r++) {
               l = Math.min(M, M - (K - 2 * (r - M)));
               l = Math.max(1, l);
               ans = Math.max(ans, prefix_sum[r] -
                   prefix_sum[l - 1]);
           }
 
           for (l = M; l > 0 && l >= M - K; l--) {
               r = Math.max(M, M + (K - 2 * (M - l)));
               r = Math.min(MX - 1, r);
               ans = Math.max(ans, prefix_sum[r] -
                   prefix_sum[l - 1]);
           }
           return ans;
       }
 
       // Driver code
       let arr = [[2, 8], [6, 3], [8, 6]];
       let M = 5;
       let K = 4;
       document.write(maxTotalPoints(arr, M, K));
 
 // This code is contributed by Potta Lokesh
   </script>

9

Complejidad Temporal: O(X), donde X es la posición máxima
Espacio Auxiliar: O(X)