Valor máximo obtenido al realizar determinadas operaciones en un Array

Dada una array arr[] , la tarea es encontrar el valor máximo que se puede obtener. El usuario puede sumar o multiplicar los dos elementos consecutivos. Sin embargo, tiene que haber al menos una operación de suma entre dos operaciones de multiplicación (es decir, no se permiten dos operaciones de multiplicación consecutivas).
Deje que los elementos de la array sean 1, 2, 3, 4 , entonces 1 * 2 + 3 + 4 es una operación válida, mientras que 1 + 2 * 3 * 4 no es una operación válida ya que hay operaciones de multiplicación consecutivas.
Ejemplos: 
 

Input : 5 -1 -5 -3 2 9 -4
Output : 33
Explanation:
The maximum value obtained by following the above conditions is 33. 
The sequence of operations are given as:
5 + (-1) + (-5) * (-3) + 2 * 9 + (-4) = 33

Input : 5 -3 -5 2 3 9 4
Output : 62

Enfoque:
Este problema se puede resolver mediante el uso de programación dinámica. 
 

1. Suponiendo una array 2D dp[][] de dimensiones n * 2.
2. dp[i][0] representa el valor máximo de la array hasta la i-ésima posición si la última operación es una suma.
3. dp[i][1] representa el valor máximo del arreglo hasta la i-ésima posición si la última operación es la multiplicación.

Ahora, dado que la operación de multiplicación consecutiva no está permitida, la relación de recurrencia se puede considerar como: 
 

dp[i][0] = max(dp[ i - 1][0], dp[ i - 1][1]) + a[ i + 1];
dp[i][1] = dp[i - 1][0] - a[i] + a[i] * a[i + 1];

Los casos base son: 
 

dp[0][0] = a[0] + a[1];
dp[0][1] = a[0] * a[1];

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// A function to calculate the maximum value
void findMax(int a[], int n)
{
    int dp[n][2];
    memset(dp, 0, sizeof(dp));
     
    // basecases
    dp[0][0] = a[0] + a[1];
    dp[0][1] = a[0] * a[1];
    
    //Loop to iterate and add the max value in the dp array
    for (int i = 1; i <= n - 2; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i + 1];
        dp[i][1] = dp[i - 1][0] - a[i] + a[i] * a[i + 1];
    }
 
    cout << max(dp[n - 2][0], dp[n - 2][1]);
}
 
// Driver Code
int main()
{
    int arr[] = { 5, -1, -5, -3, 2, 9, -4 };
    findMax(arr, 7);
}

// Java implementation of the above approach
class GFG
{
     
    // A function to calculate the maximum value
    static void findMax(int []a, int n)
    {
        int dp[][] = new int[n][2];
        int i, j;
         
        for (i = 0; i < n ; i++)
            for(j = 0; j < 2; j++)
                dp[i][j] = 0;
 
        // basecases
        dp[0][0] = a[0] + a[1];
        dp[0][1] = a[0] * a[1];
         
        // Loop to iterate and add the
        // max value in the dp array
        for (i = 1; i <= n - 2; i++)
        {
            dp[i][0] = Math.max(dp[i - 1][0],
                                dp[i - 1][1]) + a[i + 1];
            dp[i][1] = dp[i - 1][0] - a[i] +
                        a[i] * a[i + 1];
        }
     
        System.out.println(Math.max(dp[n - 2][0],
                                    dp[n - 2][1]));
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { 5, -1, -5, -3, 2, 9, -4 };
        findMax(arr, 7);
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the above approach
import numpy as np
 
# A function to calculate the maximum value
def findMax(a, n) :
 
    dp = np.zeros((n, 2));
     
    # basecases
    dp[0][0] = a[0] + a[1];
    dp[0][1] = a[0] * a[1];
     
    # Loop to iterate and add the max value in the dp array
    for i in range(1, n - 1) :
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i + 1];
        dp[i][1] = dp[i - 1][0] - a[i] + a[i] * a[i + 1];
 
    print(max(dp[n - 2][0], dp[n - 2][1]), end ="");
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 5, -1, -5, -3, 2, 9, -4 ];
    findMax(arr, 7);
     
# This code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
 
class GFG
{
     
    // A function to calculate the maximum value
    static void findMax(int []a, int n)
    {
        int [,]dp = new int[n, 2];
        int i, j;
         
        for (i = 0; i < n ; i++)
            for(j = 0; j < 2; j++)
                dp[i, j] = 0;
 
        // basecases
        dp[0, 0] = a[0] + a[1];
        dp[0, 1] = a[0] * a[1];
         
        // Loop to iterate and add the
        // max value in the dp array
        for (i = 1; i <= n - 2; i++)
        {
            dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1]) + a[i + 1];
                                 
            dp[i, 1] = dp[i - 1, 0] - a[i] + a[i] * a[i + 1];
        }
     
        Console.WriteLine(Math.Max(dp[n - 2, 0], dp[n - 2, 1]));
    }
     
    // Driver Code
    public static void Main()
    {
        int []arr = { 5, -1, -5, -3, 2, 9, -4 };
        findMax(arr, 7);
    }
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation of the above approach
// A function to calculate the maximum value
    function findMax(a , n) {
        var dp = Array(n).fill().map(()=>Array(2).fill(0));
        var i, j;
 
        for (i = 0; i < n; i++)
            for (j = 0; j < 2; j++)
                dp[i][j] = 0;
 
        // basecases
        dp[0][0] = a[0] + a[1];
        dp[0][1] = a[0] * a[1];
 
        // Loop to iterate and add the
        // max value in the dp array
        for (i = 1; i <= n - 2; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]) + a[i + 1];
            dp[i][1] = dp[i - 1][0] - a[i] + a[i] * a[i + 1];
        }
 
        document.write(Math.max(dp[n - 2][0], dp[n - 2][1]));
    }
 
    // Driver Code
     
        var arr = [ 5, -1, -5, -3, 2, 9, -4 ];
        findMax(arr, 7);
 
// This code contributed by Rajput-Ji
</script>

33