Suma máxima de la array después de dividirla en tres segmentos

Dada una array a de tamaño N . La tarea es encontrar la suma máxima posible del arreglo dividiendo el arreglo en tres segmentos de manera que cada elemento en el primer segmento se multiplique por -1 y cada elemento en el segundo segmento se multiplique por 1 y cada elemento en el tercer segmento sea multiplicado por -1. Los segmentos pueden intersecarse y cualquier segmento puede incluir cero en él.

Ejemplos: 

Entrada: a[] = {-6, 10, -3, 10, -2} 
Salida: 25 
Divide los segmentos como {-6}, {10, -3, 10}, {-2)

Entrada: a[] = {-6, -10} 
Salida: 16 

Enfoque: Lo 
primero que necesitamos es calcular para todas las situaciones posibles para cada i-ésimo elemento donde se debe realizar la división.  

  • En el primer recorrido, encuentre si el i-ésimo elemento produce la suma máxima multiplicando por -1 o manteniéndolo como está.
  • Almacene todos los valores en la array b .
  • En el segundo recorrido, encuentre la suma máxima disminuyendo a[i] y agregándole b[i] .

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

C++

// C++ program to find maximum sum of array
// after dividing it into three segments
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum sum of array
// after dividing it into three segments
int Max_Sum(int a[], int n)
{
    // To store sum upto ith index
    int b[n];
    int S = 0;
    int res = 0;
     
    // Traverse through the array
    for (int i = 0; i < n; i++)
    {
        b[i] = res;
        res += a[i];
        S += a[i];
         
        // Get the maximum possible sum
        res = max(res, -S);
    }
     
    // Store in the required answer
    int ans = S;
     
    // Maximum sum starting from left segment
    // by choosing between keeping array element as
    // it is or subtracting it
    ans = max(ans, res);
 
 
    // Finding maximum sum by decreasing a[i] and
    // adding b[i] to it that means max(multiplying
    // it by -1 or using b[i] value)
    int g = 0;
     
    // For third segment
    for (int i = n - 1; i >= 0; --i) {
        g -= a[i];
        ans = max(ans, g + b[i]);
    }
     
    // return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { -6, 10, -3, 10, -2 };
 
    int n = sizeof(a) / sizeof(a[0]);
     
    // Function call
    cout << "Maximum sum is: " << Max_Sum(a, n);
 
    return 0;
}

Java

// Java program to find maximum sum of array
// after dividing it into three segments
import java.util.*;
 
class GFG
{
 
// Function to find maximum sum of array
// after dividing it into three segments
static int Max_Sum(int a[], int n)
{
    // To store sum upto ith index
    int []b = new int[n];
    int S = 0;
    int res = 0;
     
    // Traverse through the array
    for (int i = 0; i < n; i++)
    {
        b[i] = res;
        res += a[i];
        S += a[i];
         
        // Get the maximum possible sum
        res = Math.max(res, -S);
    }
     
    // Store in the required answer
    int ans = S;
     
    // Maximum sum starting from left segment
    // by choosing between keeping array element as
    // it is or subtracting it
    ans = Math.max(ans, res);
 
    // Finding maximum sum by decreasing a[i] and
    // adding b[i] to it that means max(multiplying
    // it by -1 or using b[i] value)
    int g = 0;
     
    // For third segment
    for (int i = n - 1; i >= 0; --i)
    {
        g -= a[i];
        ans = Math.max(ans, g + b[i]);
    }
     
    // return the required answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { -6, 10, -3, 10, -2 };
 
    int n = a.length;
     
    // Function call
    System.out.println("Maximum sum is: " +
                            Max_Sum(a, n));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to find
# maximum sum of array after
# dividing it into three segments
 
# Function to find maximum sum of array
# after dividing it into three segments
def Max_Sum(a, n):
     
    # To store sum upto ith index
    b = [0 for i in range(n)]
    S = 0
    res = 0
 
    # Traverse through the array
    for i in range(n):
        b[i] = res
        res += a[i]
        S += a[i]
 
        # Get the maximum possible sum
        res = max(res, -S)
 
    # Store in the required answer
    ans = S
 
    # Maximum sum starting from
    # left segment by choosing between
    # keeping array element as it is
    # or subtracting it
    ans = max(ans, res)
 
    # Finding maximum sum by decreasing
    # a[i] and adding b[i] to it
    # that means max(multiplying it
    # by -1 or using b[i] value)
    g = 0
 
    # For third segment
    for i in range(n - 1, -1, -1):
        g -= a[i]
        ans = max(ans, g + b[i])
 
    # return the required answer
    return ans
 
# Driver code
a = [-6, 10, -3, 10, -2]
 
n = len(a)
 
# Function call
print("Maximum sum is:",
          Max_Sum(a, n))
            
# This code is contributed
# by Mohit Kumar

C#

// C#+ program to find maximum sum of array
// after dividing it into three segments
using System;
 
class GFG
{
 
// Function to find maximum sum of array
// after dividing it into three segments
static int Max_Sum(int []a, int n)
{
    // To store sum upto ith index
    int []b = new int[n];
    int S = 0;
    int res = 0;
     
    // Traverse through the array
    for (int i = 0; i < n; i++)
    {
        b[i] = res;
        res += a[i];
        S += a[i];
         
        // Get the maximum possible sum
        res = Math.Max(res, -S);
    }
     
    // Store in the required answer
    int ans = S;
     
    // Maximum sum starting from left segment
    // by choosing between keeping array element
    // as it is or subtracting it
    ans = Math.Max(ans, res);
 
    // Finding maximum sum by decreasing a[i] and
    // adding b[i] to it that means max(multiplying
    // it by -1 or using b[i] value)
    int g = 0;
     
    // For third segment
    for (int i = n - 1; i >= 0; --i)
    {
        g -= a[i];
        ans = Math.Max(ans, g + b[i]);
    }
     
    // return the required answer
    return ans;
}
 
// Driver code
public static void Main()
{
    int []a = { -6, 10, -3, 10, -2 };
 
    int n = a.Length;
     
    // Function call
    Console.WriteLine("Maximum sum is: " +
                           Max_Sum(a, n));
}
}
 
// This code is contributed by anuj_67..

PHP

<?php
// PHP program to find maximum sum of array
// after dividing it into three segments
 
// Function to find maximum sum of array
// after dividing it into three segments
function Max_Sum($a, $n)
{
    // To store sum upto ith index
    $b = array();
    $S = 0;
    $res = 0;
     
    // Traverse through the array
    for ($i = 0; $i < $n; $i++)
    {
        $b[$i] = $res;
        $res += $a[$i];
        $S += $a[$i];
         
        // Get the maximum possible sum
        $res = max($res, -$S);
    }
     
    // Store in the required answer
    $ans = $S;
     
    // Maximum sum starting from left segment
    // by choosing between keeping array element as
    // it is or subtracting it
    $ans = max($ans, $res);
 
    // Finding maximum sum by decreasing a[i] and
    // adding b[i] to it that means max(multiplying
    // it by -1 or using b[i] value)
    $g = 0;
     
    // For third segment
    for ($i = $n - 1; $i >= 0; --$i)
    {
        $g -= $a[$i];
        $ans = max($ans, $g + $b[$i]);
    }
     
    // return the required answer
    return $ans;
}
 
// Driver code
$a = array(-6, 10, -3, 10, -2 );
 
$n = count($a);
 
// Function call
echo ("Maximum sum is: ");
echo Max_Sum($a, $n);
 
// This code is contributed by Naman_garg.
?>

Javascript

<script>
    // Javascript program to find maximum sum of array
    // after dividing it into three segments
     
    // Function to find maximum sum of array
    // after dividing it into three segments
    function Max_Sum(a, n)
    {
        // To store sum upto ith index
        let b = new Array(n);
        let S = 0;
        let res = 0;
 
        // Traverse through the array
        for (let i = 0; i < n; i++)
        {
            b[i] = res;
            res += a[i];
            S += a[i];
 
            // Get the maximum possible sum
            res = Math.max(res, -S);
        }
 
        // Store in the required answer
        let ans = S;
 
        // Maximum sum starting from left segment
        // by choosing between keeping array element
        // as it is or subtracting it
        ans = Math.max(ans, res);
 
        // Finding maximum sum by decreasing a[i] and
        // adding b[i] to it that means max(multiplying
        // it by -1 or using b[i] value)
        let g = 0;
 
        // For third segment
        for (let i = n - 1; i >= 0; --i)
        {
            g -= a[i];
            ans = Math.max(ans, g + b[i]);
        }
 
        // return the required answer
        return ans;
    }
     
    let a = [ -6, 10, -3, 10, -2 ];
   
    let n = a.length;
       
    // Function call
    document.write("Maximum sum is: " +
                           Max_Sum(a, n));
 
</script>
Producción: 

Maximum sum is: 25

 

Análisis de Complejidad:

Complejidad de tiempo: O(N), ya que tenemos 2 pases del bucle de tamaño N dentro de la función Max_Sum(), por lo que la complejidad de tiempo será O(N+N)->O(N).

Complejidad espacial: O(N) , ya que hemos creado una array de tamaño N dentro de la función Max_Sum().
 

Publicación traducida automáticamente

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