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().