Maximice la suma de los elementos restantes después de cada eliminación de la mitad de la array con una suma mayor

Dada una array arr[] que consta de N enteros, la tarea es maximizar la suma resultante obtenida después de agregar los elementos restantes después de cada eliminación de la mitad de la array con la suma máxima.

La array se puede dividir en dos mitades no vacías izquierda [] y derecha [] donde izquierda [] contiene los elementos de los índices [0, N/2) y derecha [] contiene los elementos de los índices [N/2, N )

Ejemplos:

Entrada: arr[] = {6, 2, 3, 4, 5, 5} 
Salida: 18 
Explicación: 
La array dada es arr[] = {6, 2, 3, 4, 5, 5} 
Paso 1: 
Suma de mitad izquierda = 6 + 2 + 3 = 11 
Suma de la mitad derecha = 4 + 5 + 5 = 12 
Suma resultante S = 11.
Paso 2: 
el arreglo modificado es arr[] = {6, 2, 3} 
Suma de la mitad izquierda = 6 
Suma de la mitad derecha = 2 + 3 = 5 
Suma resultante S = 11 + 5 = 16
Paso 3: 
el arreglo modificado es arr[] = {2, 3} 
Suma de la mitad izquierda = 2 
Suma de la mitad derecha = 3 
Suma resultante S = 16 + 2 = 18.
Por lo tanto, la suma resultante es 18.

Entrada: arr[] = {4} 
Salida: 0

Enfoque ingenuo: el enfoque más simple para resolver el problema es usar la recursividad . A continuación se muestran los pasos:

  1. Use el concepto de suma de prefijos e inicialice una variable, digamos res para almacenar el resultado final .
  2. Crea un diccionario .
  3. Recorra la array y almacene toda la suma de prefijos en el diccionario.
  4. Ahora, itere sobre el rango [0, N] y almacene la suma del prefijo de las mitades izquierda y derecha de la array como izquierda y derecha respectivamente.
  5. Ahora, hay tres condiciones posibles: 
    • izquierda > derecha
    • izquierda <derecha
    • izquierda == derecha
  6. Para todas las condiciones anteriores, ignore la suma máxima y agregue la suma mínima entre la izquierda y la derecha a la suma resultante y continúe con las llamadas recursivas.
  7. Después de que finalice toda la llamada recursiva, imprima el valor máximo de la suma resultante .

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

C++14

// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum sum
int maxweight(int s, int e,
  unordered_map<int, int>& pre)
{
     
    // Base case
    // len of array is 1
    if (s == e)
        return 0;
 
    // Stores the final result
    int ans = 0;
 
    // Traverse the array
    for(int i = s; i < e; i++)
    {
         
        // Store left prefix sum
        int left = pre[i] - pre[s - 1];
 
        // Store right prefix sum
        int right = pre[e] - pre[i];
 
        // Compare the left and right
        if (left < right)
            ans = max(ans, left +
                      maxweight(s, i, pre));
 
        // If both are equal apply
        // the optimal method
        if (left == right)
        {
            // Update with minimum
            ans = max({ans, left +
                       maxweight(s, i, pre),
                             right +
                       maxweight(i + 1, e, pre)});
        }
 
        if (left > right)
            ans = max(ans, right +
                     maxweight(i + 1, e, pre));
    }    
 
    // Return the final ans
    return ans;
}
 
// Function to print maximum sum
void maxSum(vector<int> arr)
{
     
    // Dictionary to store prefix sums
    unordered_map<int, int> pre;
    pre[-1] = 0;
    pre[0] = arr[0];
 
    // Traversing the array
    for(int i = 1; i < arr.size(); i++)
    {
         
        // Add prefix sum of the array
        pre[i] = pre[i - 1] + arr[i];
    }
    cout << maxweight(0, arr.size() - 1, pre);
}
 
// Driver Code
int main()
{
    vector<int> arr = { 6, 2, 3, 4, 5, 5 };
     
    // Function call
    maxSum(arr);
     
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Function to find the maximum sum
static int maxweight(int s, int e,
                     Map<Integer, Integer> pre)
{
     
    // Base case
    // len of array is 1
    if (s == e)
        return 0;
 
    // Stores the final result
    int ans = 0;
 
    // Traverse the array
    for(int i = s; i < e; i++)
    {
         
        // Store left prefix sum
        int left = pre.get(i) - pre.get(s - 1);
 
        // Store right prefix sum
        int right = pre.get(e) - pre.get(i);
 
        // Compare the left and right
        if (left < right)
            ans = Math.max(ans, left +
                           maxweight(s, i, pre));
 
        // If both are equal apply
        // the optimal method
        if (left == right)
        {
             
            // Update with minimum
            ans = Math.max(ans, Math.max(left +
                           maxweight(s, i, pre),
                           right + maxweight(i + 1,
                                             e, pre)));
        }
 
        if (left > right)
            ans = Math.max(ans, right +
                           maxweight(i + 1, e, pre));
    }    
     
    // Return the final ans
    return ans;
}
 
// Function to print maximum sum
static void maxSum(List<Integer> arr)
{
     
    // To store prefix sums
    Map<Integer, Integer> pre = new HashMap<>();
    pre.put(-1, 0);
    pre.put(0, arr.get(0));
 
    // Traversing the array
    for(int i = 1; i < arr.size(); i++)
    {
         
        // Add prefix sum of the array
        pre.put(i, pre.getOrDefault(i - 1, 0) +
                   arr.get(i));
    }
    System.out.println(maxweight(0,
                arr.size() - 1, pre));
}
 
// Driver code
public static void main (String[] args)
{
    List<Integer> arr = Arrays.asList(6, 2, 3,
                                      4, 5, 5);
     
    // Function call
    maxSum(arr);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program to implement
# the above approach
 
# Function to find the maximum sum
def maxweight(s, e, pre):
 
    # Base case
    # len of array is 1
    if s == e:
        return 0
 
    # Stores the final result
    ans = 0
 
    # Traverse the array
    for i in range(s, e):
 
        # Store left prefix sum
        left = pre[i] - pre[s - 1]
 
        # Store right prefix sum
        right = pre[e] - pre[i]
 
        # Compare the left and right
        if left < right:
            ans = max(ans, left \
            + maxweight(s, i, pre))
 
        # If both are equal apply
        # the optimal method
        if left == right:
 
            # Update with minimum
            ans = max(ans, left \
                  + maxweight(s, i, pre),
                    right \
                  + maxweight(i + 1, e, pre))
 
        if left > right:
            ans = max(ans, right \
                  + maxweight(i + 1, e, pre))
 
    # Return the final ans
    return ans
 
# Function to print maximum sum
def maxSum(arr):
 
    # Dictionary to store prefix sums
    pre = {-1: 0, 0: arr[0]}
 
    # Traversing the array
    for i in range(1, len(arr)):
 
        # Add prefix sum of the array
        pre[i] = pre[i - 1] + arr[i]
     
    print(maxweight(0, len(arr) - 1, pre))
 
# Drivers Code
 
arr = [6, 2, 3, 4, 5, 5]
 
# Function Call
maxSum(arr)

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
     
// Function to find the maximum sum
static int maxweight(int s, int e,
                     Dictionary<int,
                     int> pre)
{
  // Base case
  // len of array is 1
  if (s == e)
    return 0;
 
  // Stores the
  // readonly result
  int ans = 0;
 
  // Traverse the array
  for(int i = s; i < e; i++)
  {
    // Store left prefix sum
    int left = pre[i] - pre[s - 1];
 
    // Store right prefix sum
    int right = pre[e] - pre[i];
 
    // Compare the left and right
    if (left < right)
      ans = Math.Max(ans, left +
            maxweight(s, i, pre));
 
    // If both are equal apply
    // the optimal method
    if (left == right)
    {
      // Update with minimum
      ans = Math.Max(ans, Math.Max(left +
                          maxweight(s, i, pre),
                          right + maxweight(i + 1,
                                            e, pre)));
    }
 
    if (left > right)
      ans = Math.Max(ans, right +
            maxweight(i + 1, e, pre));
  }    
 
  // Return the readonly ans
  return ans;
}
 
// Function to print maximum sum
static void maxSum(List<int> arr)
{
     
  // To store prefix sums
  Dictionary<int,
             int> pre = new Dictionary<int,
                                       int>();
  pre.Add(-1, 0);
  pre.Add(0, arr[0]);
 
  // Traversing the array
  for(int i = 1; i < arr.Count; i++)
  {
    // Add prefix sum of the array
    if(pre[i - 1] != 0)
      pre.Add(i, pre[i - 1] + arr[i]);
    else
      pre.Add(i, arr[i]);
  }
  Console.WriteLine(maxweight(0,
                    arr.Count - 1, pre));
}
 
// Driver code
public static void Main(String[] args)
{
  List<int> arr = new List<int>();
  arr.Add(6);
  arr.Add(2);
  arr.Add(3);
  arr.Add(4);
  arr.Add(5);
  arr.Add(5);
 
  // Function call
  maxSum(arr);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// js program to implement
// the above approach
 
// Function to find the maximum sum
function maxweight(s, e, pre){
    // Base case
    // len of array is 1
    if (s == e)
        return 0;
 
    // Stores the final result
    let ans = 0;
 
    // Traverse the array
    for(let i = s; i < e; i++)
    {
         
        // Store left prefix sum
        if(!pre[i])
           pre[i] = 0;
        if(!pre[e])
           pre[e] = 0;
        if(!pre[s-1])
           pre[s-1] = 0;
        let left = pre[i] - pre[s - 1];
 
        // Store right prefix sum
        let right = pre[e] - pre[i];
 
        // Compare the left and right
        if (left < right)
            ans = Math.max(ans, left +
                      maxweight(s, i, pre));
 
        // If both are equal apply
        // the optimal method
        if (left == right)
        {
            // Update with minimum
            ans = Math.max(ans, Math.max(left +
                       maxweight(s, i, pre),
                             right +
                       maxweight(i + 1, e, pre)));
        }
 
        if (left > right)
            ans = Math.max(ans, right +
                     maxweight(i + 1, e, pre));
    }    
 
    // Return the final ans
    return ans;
}
 
// Function to print maximum sum
function maxSum(arr)
{
     
    // Dictionary to store prefix sums
    let pre = new Map;
    pre[-1] = 0;
    pre[0] = arr[0];
 
    // Traversing the array
    for(let i = 1; i < arr.length; i++)
    {
         
        // Add prefix sum of the array
        pre[i] = pre[i - 1] + arr[i];
    }
   document.write( maxweight(0, arr.length - 1, pre));
}
 
// Driver Code
arr = [ 6, 2, 3, 4, 5, 5 ];
// Function call
 maxSum(arr);
 
 
</script>
Producción: 

18

Complejidad de Tiempo: O(2 N
Espacio Auxiliar: O(N 2 )

Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que hay una serie de subproblemas superpuestos repetidos . 
Por lo tanto, para la optimización, utilice Programación Dinámica . La idea es usar un diccionario y realizar un seguimiento de los valores de los resultados para que cuando se requieran en cálculos posteriores se pueda acceder a ellos sin tener que volver a calcularlos.

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
int dp[100][100];
 
// Function to find the maximum sum
int maxweight(int s, int e,
          map<int, int> pre)
{
     
    // Base Case
    if (s == e)
        return 0;
 
    // Create a key to map
    // the values
 
    // Check if (mapped key is
    // found in the dictionary
    if (dp[s][e] != -1)
        return dp[s][e];
 
    int ans = 0;
 
    // Traverse the array
    for(int i = s; i < e; i++)
    {
         
        // Store left prefix sum
        int left = pre[i] - pre[s - 1];
 
        // Store right prefix sum
        int right = pre[e] - pre[i];
 
        // Compare the left and
        // right values
        if (left < right)
            ans = max(
                ans, (int)(left +
                           maxweight(s, i, pre)));
 
        if (left == right)
            ans = max(
                ans, max(left + maxweight(s, i,
                                          pre),
                         right + maxweight(i + 1,
                                           e, pre)));
 
        if (left > right)
            ans = max(
                ans, right + maxweight(i + 1, e, pre));
 
        // Store the value in dp array
        dp[s][e] = ans;
    }
 
    // Return the final answer
    return dp[s][e];
}
 
// Function to print maximum sum
void maxSum(int arr[], int n)
{
     
    // Stores prefix sum
    map<int, int> pre;
    pre[-1] = 0;
    pre[0] = arr[0];
 
    // Store results of subproblems
    memset(dp, -1, sizeof dp);
 
    // Traversing the array
    for(int i = 0; i < n; i++)
 
        // Add prefix sum of array
        pre[i] = pre[i - 1] + arr[i];
 
    // Print the answer
    cout << (maxweight(0, n - 1, pre));
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 2, 3, 4, 5, 5 };
 
    // Function call
    maxSum(arr, 6);
}
 
// This code is contributed by grand_master

Java

// Java program to implement
// the above approach
import java.util.*;
 
class solution{
    
static int[][] dp = new int[100][100];
 
// Function to find the maximum sum
static int maxweight(int s, int e,
                     HashMap<Integer, Integer> pre)
{
     
    // Base Case
    if (s == e)
        return 0;
 
    // Create a key to map
    // the values
 
    // Check if (mapped key is
    // found in the dictionary
    if (dp[s][e] != -1)
        return dp[s][e];
 
    int ans = 0;
 
    // Traverse the array
    for(int i = s; i < e; i++)
    {
         
        // Store left prefix sum
        int left = pre.get(i) -
                   pre.get(s - 1);
 
        // Store right prefix sum
        int right = pre.get(e) -
                    pre.get(i);
 
        // Compare the left and
        // right values
        if (left < right)
            ans = Math.max(ans, (int)(left +
                           maxweight(s, i, pre)));
 
        if (left == right)
            ans = Math.max(ans,
                           Math.max(left + maxweight(s, i,
                                                     pre),
                                    right + maxweight(i + 1,
                                                      e, pre)));
 
        if (left > right)
            ans = Math.max(ans, right + maxweight(i + 1,
                                                  e, pre));
 
        // Store the value in dp array
        dp[s][e] = ans;
    }
     
    // Return the final answer
    return dp[s][e];
}
 
// Function to print maximum sum
static void maxSum(int arr[], int n)
{
     
    // Stores prefix sum
    HashMap<Integer,
            Integer> pre = new HashMap<Integer,
                                       Integer>();
    pre.put(-1, 0);
    pre.put(0, arr[0]);
 
    // Store results of subproblems
    for(int i = 0; i < 100; i++)
    {
        for(int j = 0; j < 100; j++)
          dp[i][j] = -1;
    }
 
    // Traversing the array
    for(int i = 0; i < n; i++)
 
        // Add prefix sum of array
        pre.put(i, pre.get(i - 1) + arr[i]);
 
    // Print the answer
    System.out.print((maxweight(0, n - 1, pre)));
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 6, 2, 3, 4, 5, 5 };
     
    // Function call
    maxSum(arr, 6);
}
}
 
// This code is contributed by Surendra_Gangwar

Python3

# Python3 program to implement
# the above approach
 
# Function to find the maximum sum
def maxweight(s, e, pre, dp):
 
    # Base Case 
    if s == e:
        return 0
 
    # Create a key to map
    # the values
    key = (s, e)
    
    # Check if mapped key is
    # found in the dictionary
    if key in dp:
        return dp[key]
 
    ans = 0
 
    # Traverse the array
    for i in range(s, e):
 
         # Store left prefix sum
        left = pre[i] - pre[s-1]
  
        # Store right prefix sum
        right = pre[e] - pre[i]
 
        # Compare the left and
        # right values
        if left < right:
            ans = max(ans, left \
                + maxweight(s, i, pre, dp))
 
        if left == right:
 
            # Update with minimum
            ans = max(ans, left \
                  + maxweight(s, i, pre, dp),
                  right \
                  + maxweight(i + 1, e, pre, dp))
 
        if left > right:
           ans = max(ans, right \
                 + maxweight(i + 1, e, pre, dp))
 
        # Store the value in dp array
        dp[key] = ans
 
    # Return the final answer
    return dp[key]
 
# Function to print maximum sum
def maxSum(arr):
 
    # Stores prefix sum
    pre = {-1: 0, 0: arr[0]}
 
    # Store results of subproblems
    dp = {}
 
    # Traversing the array
    for i in range(1, len(arr)):
         
        # Add prefix sum of array
        pre[i] = pre[i - 1] + arr[i]
 
    # Print the answer
    print(maxweight(0, len(arr) - 1, pre, dp))
 
# Driver Code
 
arr = [6, 2, 3, 4, 5, 5]
 
# Function Call
maxSum(arr)

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
    
static int[,] dp = new int[100, 100];
 
// Function to find the maximum sum
static int maxweight(int s, int e,
          Dictionary<int, int> pre)
{
     
    // Base Case
    if (s == e)
        return 0;
 
    // Create a key to map
    // the values
 
    // Check if (mapped key is
    // found in the dictionary
    if (dp[s, e] != -1)
        return dp[s, e];
 
    int ans = 0;
 
    // Traverse the array
    for(int i = s; i < e; i++)
    {
         
        // Store left prefix sum
        int left = pre[i] -
                   pre[s - 1];
 
        // Store right prefix sum
        int right = pre[e] -
                    pre[i];
 
        // Compare the left and
        // right values
        if (left < right)
            ans = Math.Max(ans, (int)(left +
                           maxweight(s, i, pre)));
 
        if (left == right)
            ans = Math.Max(ans,
                           Math.Max(left + maxweight(s, i,
                                                     pre),
                                   right + maxweight(i + 1,
                                                     e, pre)));
 
        if (left > right)
            ans = Math.Max(ans, right + maxweight(i + 1,
                                                  e, pre));
 
        // Store the value in dp array
        dp[s, e] = ans;
    }
     
    // Return the readonly answer
    return dp[s, e];
}
 
// Function to print maximum sum
static void maxSum(int []arr, int n)
{
     
    // Stores prefix sum
    Dictionary<int,
               int> pre = new Dictionary<int,
                                         int>();
    pre.Add(-1, 0);
    pre.Add(0, arr[0]);
 
    // Store results of subproblems
    for(int i = 0; i < 100; i++)
    {
        for(int j = 0; j < 100; j++)
          dp[i, j] = -1;
    }
 
    // Traversing the array
    for(int i = 1; i < n; i++)
 
        // Add prefix sum of array
        pre.Add(i, pre[i - 1] + arr[i]);
 
    // Print the answer
    Console.Write((maxweight(0, n - 1, pre)));
}
 
// Driver Code
public static void Main(String []args)
{
    int []arr = { 6, 2, 3, 4, 5, 5 };
     
    // Function call
    maxSum(arr, 6);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// js program to implement
// the above approach
let dp=[];
for(let i = 0;i<100;i++){
dp[i] = [];
for(let j = 0;j<100;j++){
dp[i][j] = 0;
}
}
 
// Function to find the maximum sum
function maxweight( s,  e, pre)
{
     
    // Base Case
    if (s == e)
        return 0;
 
    // Create a key to map
    // the values
 
    // Check if (mapped key is
    // found in the dictionary
    if (dp[s][e] != -1)
        return dp[s][e];
 
    let ans = 0;
 
    // Traverse the array
    for(let i = s; i < e; i++)
    {
         
        // Store left prefix sum
        let left = pre[i] - pre[s - 1];
 
        // Store right prefix sum
        let right = pre[e] - pre[i];
 
        // Compare the left and
        // right values
        if (left < right)
            ans = Math.max(
                ans, Number(left +
                           maxweight(s, i, pre)));
 
        if (left == right)
            ans = Math.max(
                ans,Math. max(left + maxweight(s, i,
                                          pre),
                         right + maxweight(i + 1,
                                           e, pre)));
 
        if (left > right)
            ans = Math.max(
                ans, right + maxweight(i + 1, e, pre));
 
        // Store the value in dp array
        dp[s][e] = ans;
    }
 
    // Return the final answer
    return dp[s][e];
}
 
// Function to print maximum sum
function maxSum(arr, n)
{
     
    // Stores prefix sum
    let pre = new Map();
    pre[-1] = 0;
    pre[0] = arr[0];
 
    // Store results of subproblems
   
    for(let i = 0;i<100;i++){
    for(let j = 0;j<100;j++){
     dp[i][j] = -1;
}
}
    // Traversing the array
    for(let i = 0; i < n; i++)
 
        // Add prefix sum of array
        pre[i] = pre[i - 1] + arr[i];
 
    // Print the answer
    document.write(maxweight(0, n - 1, pre));
}
 
// Driver Code
let arr= [ 6, 2, 3, 4, 5, 5 ];
 
    // Function call
    maxSum(arr, 6);
 
</script>
Producción: 

18

Complejidad de Tiempo: O(N 3
Espacio Auxiliar: O(N 2 )
 

Publicación traducida automáticamente

Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *