Suma máxima de subarreglo posible reemplazando un elemento de arreglo por su cuadrado

Dada una array a[] que consta de N enteros, la tarea es encontrar la suma máxima de subarreglo que se puede obtener reemplazando un solo elemento de array por su cuadrado.

Ejemplos:

Entrada: a[] = {1, -5, 8, 12, -8} 
Salida: 152 
Explicación: 
reemplazando 12 por 144, el subarreglo {8, 144} genera la máxima suma de subarreglo posible en el arreglo.
Entrada: a[] = {-1, -2, -3} 
Salida: 9 
Explicación:

Enfoque ingenuo: el enfoque más simple para resolver el problema es reemplazar cada elemento con su cuadrado y, para cada uno de ellos, encontrar la suma máxima de subarreglo utilizando el algoritmo de Kadane . Finalmente, imprima la suma de subarreglo máxima posible obtenida. 
Complejidad de Tiempo: O(N ² ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica. Siga los pasos a continuación para resolver el problema:

• Inicialice la tabla de memorización dp[][] donde:
• dp[i][0]: Almacena la suma máxima de subarreglo que se puede obtener incluyendo el i ^-ésimo elemento y sin elevar al cuadrado ningún elemento del arreglo.
• dp[i][1]: Almacena la suma máxima de subarreglo que puede incluir el i ^-ésimo elemento y elevar al cuadrado uno de los elementos del arreglo
• Por lo tanto, las relaciones de recurrencia son:

dp[i][0] = max(dp[i-1][0] + a[i], a[i]) , es decir, extender el subarreglo anterior que termina en i – ^1th índice o comenzar uno nuevo subarreglo del i ^-ésimo índice.
dp[i][1] = max(a[i] ² , dp[i-1][0] + a[i] ² , dp[i-1][1] + a[i]) , es decir , comience un nuevo subarreglo desde i ^-ésimo índice o extienda el subarreglo anterior agregando a[i] ² a dp[i – 1][0] o agregue a[i] a dp[i – 1][1]
 

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

// C++ program to implement
// the above approach
#include <bits/stdc++.h> 
using namespace std; 
 
// Function to find the maximum subarray
// sum possible
int getMaxSum(int a[], int n)
{
    int dp[n][2];
 
    // Stores sum without squaring
    dp[0][0] = a[0];
 
    // Stores sum squaring
    dp[0][1] = a[0] * a[0];
 
    // Stores the maximum subarray sum
    int max_sum = max(dp[0][0], dp[0][1]);
    for(int i = 1; i < n; i++)
    {
         
        // Either extend the subarray
        // or start a new subarray
        dp[i][0] = max(a[i],
                      dp[i - 1][0] + a[i]);
 
        // Either extend previous squared
        // subarray or start a new subarray
        // by squaring the current element
        dp[i][1] = max(dp[i - 1][1] + a[i],
                               a[i] * a[i]);
 
        dp[i][1] = max(dp[i][1],
                       dp[i - 1][0] +
                       a[i] * a[i]);
 
        // Update maximum subarray sum
        max_sum = max(max_sum, dp[i][1]);
        max_sum = max(max_sum, dp[i][0]);
    }
     
    // Return answer
    return max_sum;
}
     
// Driver Code
int32_t main()
{
    int n = 5;
    int a[] = { 1, -5, 8, 12, -8 };
 
    // Function call
    cout << getMaxSum(a, n) << endl;
 
    return 0;
}
 
// This code is contributed by rutvik_56

// Java Program to implement
// the above approach
import java.io.*;
 
class GFG {
 
    // Function to find the maximum subarray
    // sum possible
    public static int getMaxSum(int a[], int n)
    {
        int dp[][] = new int[n][2];
 
        // Stores sum without squaring
        dp[0][0] = a[0];
 
        // Stores sum squaring
        dp[0][1] = a[0] * a[0];
 
        // Stores the maximum subarray sum
        int max_sum = Math.max(dp[0][0], dp[0][1]);
        for (int i = 1; i < n; i++) {
 
            // Either extend the subarray
            // or start a new subarray
            dp[i][0] = Math.max(a[i],
                                dp[i - 1][0] + a[i]);
 
            // Either extend previous squared
            // subarray or start a new subarray
            // by squaring the current element
            dp[i][1] = Math.max(dp[i - 1][1] + a[i],
                                a[i] * a[i]);
 
            dp[i][1]
                = Math.max(dp[i][1],
                        dp[i - 1][0] + a[i] * a[i]);
 
            // Update maximum subarray sum
            max_sum = Math.max(max_sum, dp[i][1]);
            max_sum = Math.max(max_sum, dp[i][0]);
        }
 
        // Return answer
        return max_sum;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 5;
        int a[] = { 1, -5, 8, 12, -8 };
 
        // Function call
        System.out.println(getMaxSum(a, n));
    }
}

# Python3 program to implement
# the above approach
 
# Function to find the maximum subarray
# sum possible
def getMaxSum(a, n):
 
    dp = [[0 for x in range(2)]
            for y in range(n)]
 
    # Stores sum without squaring
    dp[0][0] = a[0]
 
    # Stores sum squaring
    dp[0][1] = a[0] * a[0]
 
    # Stores the maximum subarray sum
    max_sum = max(dp[0][0], dp[0][1])
 
    for i in range(1, n):
 
        # Either extend the subarray
        # or start a new subarray
        dp[i][0] = max(a[i],
                    dp[i - 1][0] + a[i])
 
        # Either extend previous squared
        # subarray or start a new subarray
        # by squaring the current element
        dp[i][1] = max(dp[i - 1][1] + a[i],
                        a[i] * a[i])
 
        dp[i][1] = max(dp[i][1],
                    dp[i - 1][0] +
                        a[i] * a[i])
 
        # Update maximum subarray sum
        max_sum = max(max_sum, dp[i][1])
        max_sum = max(max_sum, dp[i][0])
 
    # Return answer
    return max_sum
 
# Driver Code
n = 5
a = [ 1, -5, 8, 12, -8 ]
 
# Function call
print(getMaxSum(a, n))
 
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find the maximum subarray
// sum possible
public static int getMaxSum(int []a, int n)
{
    int [,]dp = new int[n, 2];
 
    // Stores sum without squaring
    dp[0, 0] = a[0];
 
    // Stores sum squaring
    dp[0, 1] = a[0] * a[0];
 
    // Stores the maximum subarray sum
    int max_sum = Math.Max(dp[0, 0], dp[0, 1]);
    for(int i = 1; i < n; i++)
    {
         
        // Either extend the subarray
        // or start a new subarray
        dp[i, 0] = Math.Max(a[i],
                        dp[i - 1, 0] + a[i]);
 
        // Either extend previous squared
        // subarray or start a new subarray
        // by squaring the current element
        dp[i, 1] = Math.Max(dp[i - 1, 1] + a[i],
                            a[i] * a[i]);
 
        dp[i, 1] = Math.Max(dp[i, 1],
                            dp[i - 1, 0] +
                            a[i] * a[i]);
 
        // Update maximum subarray sum
        max_sum = Math.Max(max_sum, dp[i, 1]);
        max_sum = Math.Max(max_sum, dp[i, 0]);
    }
 
    // Return answer
    return max_sum;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 5;
    int []a = { 1, -5, 8, 12, -8 };
 
    // Function call
    Console.WriteLine(getMaxSum(a, n));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program for the above approach
 
  // Function to find the maximum subarray
    // sum possible
    function getMaxSum(a, n)
    {
        let dp = new Array(n);
        // Loop to create 2D array using 1D array
        for (var i = 0; i < dp.length; i++) {
            dp[i] = new Array(2);
        }
   
        // Stores sum without squaring
        dp[0][0] = a[0];
   
        // Stores sum squaring
        dp[0][1] = a[0] * a[0];
   
        // Stores the maximum subarray sum
        let max_sum = Math.max(dp[0][0], dp[0][1]);
        for (let i = 1; i < n; i++) {
   
            // Either extend the subarray
            // or start a new subarray
            dp[i][0] = Math.max(a[i],
                                dp[i - 1][0] + a[i]);
   
            // Either extend previous squared
            // subarray or start a new subarray
            // by squaring the current element
            dp[i][1] = Math.max(dp[i - 1][1] + a[i],
                                a[i] * a[i]);
   
            dp[i][1]
                = Math.max(dp[i][1],
                        dp[i - 1][0] + a[i] * a[i]);
   
            // Update maximum subarray sum
            max_sum = Math.max(max_sum, dp[i][1]);
            max_sum = Math.max(max_sum, dp[i][0]);
        }
   
        // Return answer
        return max_sum;
    }
     
// Driver Code
 
        let n = 5;
        let a = [ 1, -5, 8, 12, -8 ];
   
        // Function call
        document.write(getMaxSum(a, n));
      
</script>

152

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)