Suma máxima de subarreglo después de invertir como máximo dos elementos

Dada una array arr[] de elementos enteros, la tarea es encontrar la máxima suma posible de sub-arrays después de cambiar los signos de dos elementos como máximo.
Ejemplos: 
 

Entrada: arr[] = {-5, 3, 2, 7, -8, 3, 7, -9, 10, 12, -6} 
Salida: 61 
Podemos obtener 61 del índice 0 al 10 
cambiando el signo de elementos en los índices 4 y 7, es decir 
, -8 y -9. Podríamos haber elegido -5 y -6 pero esto nos da una 
suma menor de 48.
Entrada: arr[] = {-5, -3, -18, 0, -4} 
Salida: 22 
 

 

Enfoque: Este problema se puede resolver usando Programación Dinámica. Supongamos que hay n elementos en la array. Construimos nuestra solución desde la longitud más pequeña hasta la longitud más grande. 
En cada paso, cambiamos la solución para la longitud i a i+1. 
Para cada paso tenemos tres casos: 
 

  1. (Suma máxima de subarray) alterando el signo de un máximo de 0 elementos.
  2. (Suma máxima de subarray) alterando el signo de 1 elemento como máximo.
  3. (Suma máxima de subarreglo) alterando el signo de un máximo de 2 elementos.

Estos casos utilizan los valores anteriores de cada uno. 
 

  • Caso 1: Tenemos dos opciones, tomar el elemento actual o agregar el valor actual al valor anterior del mismo caso. Almacenamos el que sea mayor.
  • Caso 2: Tenemos dos opciones aquí 
    1. Alteramos el signo del elemento actual y luego lo agregamos a 0 o al valor anterior del caso 1. almacenamos el que sea más grande.
    2. tomamos el elemento actual de la array y lo agregamos al valor del caso 2 anterior. Si este valor es mayor que el valor que obtenemos en el caso (a), entonces no actualizamos.
  • Caso 3: Nuevamente tenemos dos opciones aquí 
    1. Alteramos el signo del elemento actual y lo agregamos al valor del caso 2 anterior.
    2. Agregamos el elemento actual al valor del caso 3 anterior. El valor mayor obtenido de (a) y (b) se almacena para el caso actual.

Actualizamos el valor máximo de estos 3 casos y lo almacenamos en una variable. 
Para cada caso de cada paso, tomamos el arreglo bidimensional dp[n+1][3] si el arreglo dado contiene n elementos.
 

Relación de recurrencia: 
Caso 1: dp[i][0] = max(dp[i – 1][0] + arr[i], arr[i])
Caso 2: dp[i][1] = max(max (0, dp[i – 1][0]) – arr[i], dp[i – 1][1] + arr[i])
Caso 3: dp[i][2] = max(dp[i – 1][1] – arr[i], dp[i – 1][2] + arr[i])
solución = max(solución, max(dp[i][0], dp[i][1] , pd[i][2])) 
 

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

C++

// C++ implementation of the approach
#include <algorithm>
#include <iostream>
using namespace std;
 
// Function to return the maximum required sub-array sum
int maxSum(int a[], int n)
{
    int ans = 0;
    int* arr = new int[n + 1];
 
    // Creating one based indexing
    for (int i = 1; i <= n; i++)
        arr[i] = a[i - 1];
 
    // 2d array to contain solution for each step
    int** dp = new int*[n + 1];
    for (int i = 0; i <= n; i++)
        dp[i] = new int[3];
    for (int i = 1; i <= n; ++i) {
 
        // Case 1: Choosing current or (current + previous)
        // whichever is smaller
        dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i]);
 
        // Case 2:(a) Altering sign and add to previous case 1 or
        // value 0
        dp[i][1] = max(0, dp[i - 1][0]) - arr[i];
 
        // Case 2:(b) Adding current element with previous case 2
        // and updating the maximum
        if (i >= 2)
            dp[i][1] = max(dp[i][1], dp[i - 1][1] + arr[i]);
 
        // Case 3:(a) Altering sign and add to previous case 2
        if (i >= 2)
            dp[i][2] = dp[i - 1][1] - arr[i];
 
        // Case 3:(b) Adding current element with previous case 3
        if (i >= 3)
            dp[i][2] = max(dp[i][2], dp[i - 1][2] + arr[i]);
 
        // Updating the maximum value of variable ans
        ans = max(ans, dp[i][0]);
        ans = max(ans, dp[i][1]);
        ans = max(ans, dp[i][2]);
    }
 
    // Return the final solution
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { -5, 3, 2, 7, -8, 3, 7, -9, 10, 12, -6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSum(arr, n);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
    // Function to return the maximum required sub-array sum
    static int maxSum(int []a, int n)
    {
        int ans = 0;
        int [] arr = new int[n + 1];
     
        // Creating one based indexing
        for (int i = 1; i <= n; i++)
            arr[i] = a[i - 1];
     
        // 2d array to contain solution for each step
        int [][] dp = new int [n + 1][3];
        for (int i = 1; i <= n; ++i)
        {
     
            // Case 1: Choosing current or (current + previous)
            // whichever is smaller
            dp[i][0] = Math.max(arr[i], dp[i - 1][0] + arr[i]);
     
            // Case 2:(a) Altering sign and add to previous case 1 or
            // value 0
            dp[i][1] = Math.max(0, dp[i - 1][0]) - arr[i];
     
            // Case 2:(b) Adding current element with previous case 2
            // and updating the maximum
            if (i >= 2)
                dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + arr[i]);
     
            // Case 3:(a) Altering sign and add to previous case 2
            if (i >= 2)
                dp[i][2] = dp[i - 1][1] - arr[i];
     
            // Case 3:(b) Adding current element with previous case 3
            if (i >= 3)
                dp[i][2] = Math.max(dp[i][2], dp[i - 1][2] + arr[i]);
     
            // Updating the maximum value of variable ans
            ans = Math.max(ans, dp[i][0]);
            ans = Math.max(ans, dp[i][1]);
            ans = Math.max(ans, dp[i][2]);
        }
     
        // Return the final solution
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { -5, 3, 2, 7, -8, 3, 7, -9, 10, 12, -6 };
        int n = arr.length;
        System.out.println(maxSum(arr, n));
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the approach
 
# Function to return the maximum
# required sub-array sum
def maxSum(a, n):
 
    ans = 0
    arr = [0] * (n + 1)
     
    # Creating one based indexing
    for i in range(1, n + 1):
        arr[i] = a[i - 1]
 
    # 2d array to contain solution for each step
    dp = [[0 for i in range(3)]
             for j in range(n + 1)]
    for i in range(0, n + 1):
         
        # Case 1: Choosing current or
        # (current + previous) whichever is smaller
        dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])
 
        # Case 2:(a) Altering sign and add to
        # previous case 1 or value 0
        dp[i][1] = max(0, dp[i - 1][0]) - arr[i]
 
        # Case 2:(b) Adding current element with
        # previous case 2 and updating the maximum
        if i >= 2:
            dp[i][1] = max(dp[i][1],
                           dp[i - 1][1] + arr[i])
 
        # Case 3:(a) Altering sign and
        # add to previous case 2
        if i >= 2:
            dp[i][2] = dp[i - 1][1] - arr[i]
 
        # Case 3:(b) Adding current element
        # with previous case 3
        if i >= 3:
            dp[i][2] = max(dp[i][2],
                           dp[i - 1][2] + arr[i])
 
        # Updating the maximum value
        # of variable ans
        ans = max(ans, dp[i][0])
        ans = max(ans, dp[i][1])
        ans = max(ans, dp[i][2])
     
    # Return the final solution
    return ans
 
# Driver code
if __name__ == "__main__":
 
    arr = [-5, 3, 2, 7, -8, 3,
            7, -9, 10, 12, -6]
    n = len(arr)
    print(maxSum(arr, n))
 
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to return the maximum required sub-array sum
    static int maxSum(int [] a, int n)
    {
        int ans = 0;
        int [] arr = new int[n + 1];
     
        // Creating one based indexing
        for (int i = 1; i <= n; i++)
            arr[i] = a[i - 1];
     
        // 2d array to contain solution for each step
        int [, ] dp = new int [n + 1, 3];
        for (int i = 1; i <= n; ++i)
        {
     
            // Case 1: Choosing current or (current + previous)
            // whichever is smaller
            dp[i, 0] = Math.Max(arr[i], dp[i - 1, 0] + arr[i]);
     
            // Case 2:(a) Altering sign and add to previous case 1 or
            // value 0
            dp[i, 1] = Math.Max(0, dp[i - 1, 0]) - arr[i];
     
            // Case 2:(b) Adding current element with previous case 2
            // and updating the maximum
            if (i >= 2)
                dp[i, 1] = Math.Max(dp[i, 1], dp[i - 1, 1] + arr[i]);
     
            // Case 3:(a) Altering sign and add to previous case 2
            if (i >= 2)
                dp[i, 2] = dp[i - 1, 1] - arr[i];
     
            // Case 3:(b) Adding current element with previous case 3
            if (i >= 3)
                dp[i, 2] = Math.Max(dp[i, 2], dp[i - 1, 2] + arr[i]);
     
            // Updating the maximum value of variable ans
            ans = Math.Max(ans, dp[i, 0]);
            ans = Math.Max(ans, dp[i, 1]);
            ans = Math.Max(ans, dp[i, 2]);
        }
     
        // Return the final solution
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
        int [] arr = { -5, 3, 2, 7, -8, 3, 7, -9, 10, 12, -6 };
        int n = arr.Length;
        Console.WriteLine(maxSum(arr, n));
    }
}
 
// This code is contributed by ihritik

PHP

<?php
// PHP implementation of the approach
 
// Function to return the maximum
// required sub-array sum
function maxSum($a, $n)
{
    $ans = 0;
    $arr = array();
 
    // Creating one based indexing
    for ($i = 1; $i <= $n; $i++)
        $arr[$i] = $a[$i - 1];
 
    // 2d array to contain solution
    // for each step
    $dp = array(array());
     
    for ($i = 1; $i <= $n; ++$i)
    {
 
        // Case 1: Choosing current or (current +
        // previous) whichever is smaller
        $dp[$i][0] = max($arr[$i],
                         $dp[$i - 1][0] + $arr[$i]);
 
        // Case 2:(a) Altering sign and add to
        // previous case 1 or value 0
        $dp[$i][1] = max(0, $dp[$i - 1][0]) - $arr[$i];
 
        // Case 2:(b) Adding current element with 
        // previous case 2 and updating the maximum
        if ($i >= 2)
            $dp[$i][1] = max($dp[$i][1],
                             $dp[$i - 1][1] + $arr[$i]);
 
        // Case 3:(a) Altering sign and
        // add to previous case 2
        if ($i >= 2)
            $dp[$i][2] = $dp[$i - 1][1] - $arr[$i];
 
        // Case 3:(b) Adding current element
        // with previous case 3
        if ($i >= 3)
            $dp[$i][2] = max($dp[$i][2],
                             $dp[$i - 1][2] + $arr[$i]);
 
        // Updating the maximum value of variable ans
        $ans = max($ans, $dp[$i][0]);
        $ans = max($ans, $dp[$i][1]);
        $ans = max($ans, $dp[$i][2]);
    }
 
    // Return the final solution
    return $ans;
}
 
// Driver code
$arr = array( -5, 3, 2, 7, -8, 3,
               7, -9, 10, 12, -6 );
$n = count($arr) ;
 
echo maxSum($arr, $n);
 
// This code is contributed by Ryuga
?>

JavaScript

<script>
 
    // JavaScript implementation of the approach
     
    // Function to return the maximum required sub-array sum
    function maxSum(a, n)
    {
        let ans = 0;
        let arr = new Array(n + 1);
       
        // Creating one based indexing
        for (let i = 1; i <= n; i++)
            arr[i] = a[i - 1];
       
        // 2d array to contain solution for each step
        let dp = new Array(n + 1);
        for (let i = 0; i <= n; ++i)
        {
            dp[i] = new Array(3);
            for (let j = 0; j < 3; ++j)
            {
                dp[i][j] = 0;
            }
        }
        for (let i = 1; i <= n; ++i)
        {
       
            // Case 1: Choosing current or (current + previous)
            // whichever is smaller
            dp[i][0] = Math.max(arr[i], dp[i - 1][0] + arr[i]);
       
            // Case 2:(a) Altering sign and add to previous case 1 or
            // value 0
            dp[i][1] = Math.max(0, dp[i - 1][0]) - arr[i];
       
            // Case 2:(b) Adding current element with previous case 2
            // and updating the maximum
            if (i >= 2)
                dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + arr[i]);
       
            // Case 3:(a) Altering sign and add to previous case 2
            if (i >= 2)
                dp[i][2] = dp[i - 1][1] - arr[i];
       
            // Case 3:(b) Adding current element with previous case 3
            if (i >= 3)
                dp[i][2] = Math.max(dp[i][2], dp[i - 1][2] + arr[i]);
       
            // Updating the maximum value of variable ans
            ans = Math.max(ans, dp[i][0]);
            ans = Math.max(ans, dp[i][1]);
            ans = Math.max(ans, dp[i][2]);
        }
       
        // Return the final solution
        return ans;
    }
     
    let arr = [ -5, 3, 2, 7, -8, 3, 7, -9, 10, 12, -6 ];
    let n = arr.length;
    document.write(maxSum(arr, n));
 
</script>
Producción: 

61

 

Complejidad de tiempo:  EN)
Complejidad de espacio: O(3*N+N) = O(N)
 

Publicación traducida automáticamente

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