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 
 

Haga clic aquí para el curso completo!

 

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:  
Complejidad de espacio: