Suma mínima posible de elementos de array después de realizar la operación dada

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N y un número X. Si cualquier subarray de la array (posiblemente vacía) arr[i], arr[i+1], … se puede reemplazar con arr[i]/x, arr[i+1]/x, …. La tarea es encontrar la suma mínima posible de la array que se puede obtener. 
Nota: La operación dada solo se puede realizar una vez.
Ejemplos: 
 

Entrada: N = 3, X = 2, arr[] = {1, -2, 3} 
Salida: 0.5 
Explicación: 
Al seleccionar el subarreglo {3} y reemplazarlo con {1.5}, el arreglo se convierte en {1, -2, 1.5}, lo que da sum = 0.5
Entrada: N = 5, X = 5, arr[] = {5, 5, 5, 5, 5} 
Salida: 5 
Explicación: 
Al seleccionar el subarreglo {5, 5, 5, 5, 5} y reemplazándolo con {1, 1, 1, 1, 1}, la suma de la array se convierte en 5. 
 

Enfoque ingenuo: un enfoque ingenuo es reemplazar todos los subconjuntos positivos posibles con los valores que obtenemos al dividirlos por X y calcular la suma. Pero el número total de subarreglos para cualquier arreglo dado es (N * (N + 1))/2 donde N es el tamaño del arreglo. Por lo tanto, el tiempo de ejecución de este algoritmo es O(N 2 ) .
Enfoque eficiente: este problema se puede resolver de manera eficiente en tiempo O (N). Observando detenidamente, se deduce que la suma puede hacerse mínima si el subarreglo a reemplazar cumple las siguientes condiciones: 
 

  1. El subarreglo debe ser positivo.
  2. La suma del subarreglo debe ser máxima.

Por lo tanto, al reducir el subarreglo que cumple las condiciones anteriores, la suma puede hacerse mínima. El subarreglo que satisface las condiciones anteriores se puede encontrar utilizando una ligera variación del algoritmo de Kadane . 
Después de encontrar la suma máxima del subarreglo, esto se puede restar de la suma del arreglo para obtener la suma mínima. Dado que la suma máxima del subarreglo se reemplaza con la suma máxima / X, este factor se puede agregar a la suma que se encuentra. Eso es: 
 

Minimum sum = (sumOfArr - subSum) + (subSum/ X)
where sumOfArr is the sum of all elements of the array
and subSum is the maximum sum of the subarray.

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

CPP

// C++ program to find the minimum possible sum
// of the array elements after performing
// the given operation
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum sum
// of the sub array
double maxSubArraySum(double a[], int size)
{
 
    // max_so_far represents the maximum sum
    // found till now and max_ending_here
    // represents the maximum sum ending at
    // a specific index
    double max_so_far = INT_MIN,
           max_ending_here = 0;
 
    // Iterating through the array to find
    // the maximum sum of the subarray
    for (int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        // If the maximum sum ending at a
        // specific index becomes less than 0,
        // then making it equal to 0.
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
// Function to find the minimum possible sum
// of the array elements after performing
// the given operation
double minPossibleSum(double a[], int n, double x)
{
    double mxSum = maxSubArraySum(a, n);
    double sum = 0;
 
    // Finding the sum of the array
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
 
    // Computing the minimum sum of the array
    sum = sum - mxSum + mxSum / x;
 
    cout << setprecision(2) << sum << endl;
}
 
// Driver code
int main()
{
    int N = 3;
    double X = 2;
    double A[N] = { 1, -2, 3 };
    minPossibleSum(A, N, X);
}

Java

// Java program to find the minimum possible sum
// of the array elements after performing
// the given operation
class GFG{
  
// Function to find the maximum sum
// of the sub array
static double maxSubArraySum(double a[], int size)
{
  
    // max_so_far represents the maximum sum
    // found till now and max_ending_here
    // represents the maximum sum ending at
    // a specific index
    double max_so_far = Integer.MIN_VALUE,
           max_ending_here = 0;
  
    // Iterating through the array to find
    // the maximum sum of the subarray
    for (int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
  
        // If the maximum sum ending at a
        // specific index becomes less than 0,
        // then making it equal to 0.
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
  
// Function to find the minimum possible sum
// of the array elements after performing
// the given operation
static void minPossibleSum(double a[], int n, double x)
{
    double mxSum = maxSubArraySum(a, n);
    double sum = 0;
  
    // Finding the sum of the array
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
  
    // Computing the minimum sum of the array
    sum = sum - mxSum + mxSum / x;
  
    System.out.print(sum +"\n");
}
  
// Driver code
public static void main(String[] args)
{
    int N = 3;
    double X = 2;
    double A[] = { 1, -2, 3 };
    minPossibleSum(A, N, X);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to find the minimum possible sum
# of the array elements after performing
# the given operation
 
# Function to find the maximum sum
# of the sub array
def maxSubArraySum(a, size):
 
    # max_so_far represents the maximum sum
    # found till now and max_ending_here
    # represents the maximum sum ending at
    # a specific index
    max_so_far = -10**9
    max_ending_here = 0
 
    # Iterating through the array to find
    # the maximum sum of the subarray
    for i in range(size):
        max_ending_here = max_ending_here + a[i]
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here
 
        # If the maximum sum ending at a
        # specific index becomes less than 0,
        # then making it equal to 0.
        if (max_ending_here < 0):
            max_ending_here = 0
    return max_so_far
 
# Function to find the minimum possible sum
# of the array elements after performing
# the given operation
def minPossibleSum(a,n, x):
    mxSum = maxSubArraySum(a, n)
    sum = 0
 
    # Finding the sum of the array
    for i in range(n):
        sum += a[i]
 
    # Computing the minimum sum of the array
    sum = sum - mxSum + mxSum / x
    print(round(sum,2))
 
# Driver code
if __name__ == '__main__':
    N = 3
    X = 2
    A=[1, -2, 3]
    minPossibleSum(A, N, X)
 
# This code is contributed by mohit kumar 29

C#

// C# program to find the minimum possible sum
// of the array elements after performing
// the given operation
using System;
 
class GFG{
   
// Function to find the maximum sum
// of the sub array
static double maxSubArraySum(double[] a, int size)
{
   
    // max_so_far represents the maximum sum
    // found till now and max_ending_here
    // represents the maximum sum ending at
    // a specific index
    double max_so_far = Int32.MinValue,
           max_ending_here = 0;
   
    // Iterating through the array to find
    // the maximum sum of the subarray
    for (int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
   
        // If the maximum sum ending at a
        // specific index becomes less than 0,
        // then making it equal to 0.
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
   
// Function to find the minimum possible sum
// of the array elements after performing
// the given operation
static void minPossibleSum(double[] a, int n, double x)
{
    double mxSum = maxSubArraySum(a, n);
    double sum = 0;
   
    // Finding the sum of the array
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
   
    // Computing the minimum sum of the array
    sum = sum - mxSum + mxSum / x;
   
    Console.Write(sum +"\n");
}
   
// Driver code
public static void Main()
{
    int N = 3;
    double X = 2;
    double[] A = { 1, -2, 3 };
    minPossibleSum(A, N, X);
}
}
 
// This code is contributed by chitranayal

Javascript

<script>
 
// Javascript program to find the minimum possible sum
// of the array elements after performing
// the given operation
 
// Function to find the maximum sum
// of the sub array
function maxSubArraySum( a, size)
{
 
    // max_so_far represents the maximum sum
    // found till now and max_ending_here
    // represents the maximum sum ending at
    // a specific index
    var max_so_far = -1000000000,
           max_ending_here = 0;
 
    // Iterating through the array to find
    // the maximum sum of the subarray
    for (var i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        // If the maximum sum ending at a
        // specific index becomes less than 0,
        // then making it equal to 0.
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
// Function to find the minimum possible sum
// of the array elements after performing
// the given operation
function minPossibleSum(a, n, x)
{
    var mxSum = maxSubArraySum(a, n);
    var sum = 0;
 
    // Finding the sum of the array
    for (var i = 0; i < n; i++) {
        sum += a[i];
    }
 
    // Computing the minimum sum of the array
    sum = sum - mxSum + mxSum / x;
 
    document.write(sum);
}
 
// Driver code
var N = 3;
var X = 2;
var A = [ 1, -2, 3 ];
minPossibleSum(A, N, X);
 
// This code is contributed by rutvik_56.
</script>
Producción: 

0.5

 

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O (N) tiempo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
 

Publicación traducida automáticamente

Artículo escrito por spp____ 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 *