Dada una array A de tamaño n , encuentre la suma máxima de subarreglo después de aplicar la operación dada como máximo dos veces. En una operación, elija cualquiera de los dos índices i y j e invierta el signo de todos los elementos del índice i al índice j, es decir, todos los elementos positivos en el rango i a j se vuelven negativos y todos los elementos negativos se vuelven positivos.
Ejemplos:
Entrada: A[] = {1, -2, -4, 3, 5, -6}
Salida: 21
Explicación:
Invertir la array del índice 1 al índice 2 y del índice 5 al índice 5 (indexación basada en 0) a obtener {1, 2, 4, 3, 5, 6} con suma máxima de subarreglo = 21Entrada: A[] = {2, -1, -18, 3, -1, -39, 5, -2}
Salida: 69
Enfoque: la idea es, en primer lugar, fusionar todos los elementos en grupos. es decir, todos los elementos positivos consecutivos se sumarán a un número entero y se colocarán en una nueva array arr y de manera similar para los elementos negativos consecutivos. Después de eso, el problema se reduce a encontrar la suma máxima del subarreglo después de invertir como máximo dos elementos de este arreglo.
La idea es usar Programación Dinámica . Ahora, cree una array dp[n][3] y aquí, en cada índice de esa array dp, mantenga tres números:
- El primer número representa la suma máxima de subarreglo después de invertir el elemento no en el arreglo. Entonces, dp[i][0] simplemente ejecutará la lógica del algoritmo de Kadane para la suma máxima de subarreglo.
- El segundo número representa la suma máxima de subarreglo después de invertir exactamente un elemento en el arreglo. Entonces, dp[i][1] será el máximo de dos valores, es decir, dp[i-1][1] + arr[i] (suma máxima de subarreglo después de invertir un elemento hasta i y luego agregarle el elemento actual) y dp[i][0]+ (-arr[i]) (es decir, la suma de subarreglo máximo no invertida anterior hasta i-1 y luego agregar el elemento actual después de invertir).
- El tercer número representa la suma máxima de subarreglo después de invertir exactamente dos elementos en el arreglo. Entonces, dp[i][2] será un máximo de dos valores, es decir
(suma máxima de subarreglo después de invertir un elemento hasta i-1 y luego agregar el elemento actual después de invertir) y (suma máxima de subarreglo después de invertir dos elementos hasta i-1 y añadiéndole el elemento actual). - Mantenga una variable maxSum que se actualizará después de cada índice y será igual al máximo del valor anterior de maxSum y los tres valores actuales, es decir, dp[i][0], dp[i][1] y dp[i] [2].
- Devuelve maxSum , que es la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to merge alternate elements into groups
// of positive and negative
void mergeElements(int n, vector<int>& arr, int* A)
{
int i = 0;
int sum = 0;
while (i < n) {
sum = 0;
while (i < n && A[i] >= 0) {
sum += A[i];
i++;
}
if (sum > 0) {
arr.push_back(sum);
}
sum = 0;
while (i < n && A[i] < 0) {
sum += A[i];
i++;
}
if (sum < 0) {
arr.push_back(sum);
}
}
}
// Function to return the maximum
// after inverting at most 2 elements
int findMaxSum(vector<int>& arr, int n)
{
int maxSum = 0;
vector<vector<int> > dp(
n,
vector<int>(3, INT_MIN));
dp[0][0] = max(0, arr[0]);
dp[0][1] = -1 * arr[0];
for (int i = 1; i < n; ++i) {
// dp[i][0] represents sum till ith index
// without inverting any element.
dp[i][0] = max(arr[i],
dp[i - 1][0] + arr[i]);
// dp[i][1] represents sum till ith index
// after inverting one element.
dp[i][1] = max(0, dp[i - 1][0]) - arr[i];
if (i >= 1) {
dp[i][1] = max(dp[i][1],
dp[i - 1][1] + arr[i]);
// dp[i][2] represents sum till ith index
// after inverting two elements.
dp[i][2] = dp[i - 1][1] - arr[i];
}
if (i >= 2) {
dp[i][2] = max(dp[i][2],
dp[i - 1][2] + arr[i]);
}
maxSum = max(maxSum, dp[i][0]);
maxSum = max(maxSum, dp[i][1]);
maxSum = max(maxSum, dp[i][2]);
}
return maxSum;
}
// Driver Code
int main()
{
int n = 8;
int A[8] = { 2, -1, -18, 3, -1, -39, 5, -2 };
// vector 'arr' contains sum of consecutive
// positive or negative elements.
vector<int> arr;
mergeElements(n, arr, A);
cout << findMaxSum(arr, arr.size());
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to merge alternate elements into groups
// of positive and negative
static Vector<Integer> mergeElements(int n, Vector<Integer> arr, int[] A)
{
int i = 0;
int sum = 0;
while (i < n) {
sum = 0;
while (i < n && A[i] >= 0) {
sum += A[i];
i++;
}
if (sum > 0) {
arr.add(sum);
}
sum = 0;
while (i < n && A[i] < 0) {
sum += A[i];
i++;
}
if (sum < 0) {
arr.add(sum);
}
}
return arr;
}
// Function to return the maximum
// after inverting at most 2 elements
static int findMaxSum(Vector<Integer> arr, int n)
{
int maxSum = 0;
int [][]dp = new int[n][3];
dp[0][0] = Math.max(0, arr.get(0));
dp[0][1] = -1 * arr.get(0);
for (int i = 1; i < n; ++i) {
// dp[i][0] represents sum till ith index
// without inverting any element.
dp[i][0] = Math.max(arr.get(i),
dp[i - 1][0] + arr.get(i));
// dp[i][1] represents sum till ith index
// after inverting one element.
dp[i][1] = Math.max(0, dp[i - 1][0]) - arr.get(i);
if (i >= 1) {
dp[i][1] = Math.max(dp[i][1],
dp[i - 1][1] + arr.get(i));
// dp[i][2] represents sum till ith index
// after inverting two elements.
dp[i][2] = dp[i - 1][1] - arr.get(i);
}
if (i >= 2) {
dp[i][2] = Math.max(dp[i][2],
dp[i - 1][2] + arr.get(i));
}
maxSum = Math.max(maxSum, dp[i][0]);
maxSum = Math.max(maxSum, dp[i][1]);
maxSum = Math.max(maxSum, dp[i][2]);
}
return maxSum;
}
// Driver Code
public static void main(String[] args)
{
int n = 8;
int A[] = { 2, -1, -18, 3, -1, -39, 5, -2 };
// vector 'arr' contains sum of consecutive
// positive or negative elements.
Vector<Integer> arr = new Vector<Integer>();
arr = mergeElements(n, arr, A);
System.out.print(findMaxSum(arr, arr.size()));
}
}
// This code is contributed by 29AjayKumar
Python3
# python program for the above approach INT_MIN = -2147483648 # Function to merge alternate elements into groups # of positive and negative def mergeElements(n, arr, A): i = 0 sum = 0 while (i < n): sum = 0 while (i < n and A[i] >= 0): sum += A[i] i += 1 if (sum > 0): arr.append(sum) sum = 0 while (i < n and A[i] < 0): sum += A[i] i += 1 if (sum < 0): arr.append(sum) # Function to return the maximum # after inverting at most 2 elements def findMaxSum(arr, n): maxSum = 0 dp = [[INT_MIN for _ in range(3)] for _ in range(n)] dp[0][0] = max(0, arr[0]) dp[0][1] = -1 * arr[0] for i in range(1, n): # dp[i][0] represents sum till ith index # without inverting any element. dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i]) # dp[i][1] represents sum till ith index # after inverting one element. dp[i][1] = max(0, dp[i - 1][0]) - arr[i] if (i >= 1): dp[i][1] = max(dp[i][1], dp[i - 1][1] + arr[i]) # dp[i][2] represents sum till ith index # after inverting two elements. dp[i][2] = dp[i - 1][1] - arr[i] if (i >= 2): dp[i][2] = max(dp[i][2], dp[i - 1][2] + arr[i]) maxSum = max(maxSum, dp[i][0]) maxSum = max(maxSum, dp[i][1]) maxSum = max(maxSum, dp[i][2]) return maxSum # Driver Code if __name__ == "__main__": n = 8 A = [2, -1, -18, 3, -1, -39, 5, -2] # vector 'arr' contains sum of consecutive # positive or negative elements. arr = [] mergeElements(n, arr, A) print(findMaxSum(arr, len(arr))) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to merge alternate elements into groups
// of positive and negative
static void mergeElements(int n, List<int> arr, int[] A)
{
int i = 0;
int sum = 0;
while (i < n) {
sum = 0;
while (i < n && A[i] >= 0) {
sum += A[i];
i++;
}
if (sum > 0) {
arr.Add(sum);
}
sum = 0;
while (i < n && A[i] < 0) {
sum += A[i];
i++;
}
if (sum < 0) {
arr.Add(sum);
}
}
}
// Function to return the maximum
// after inverting at most 2 elements
static int findMaxSum(List<int> arr, int n)
{
int maxSum = 0;
int[, ] dp = new int[n, 3];
for (int i = 0; i < n; i++)
for (int j = 0; j < 3; j++)
dp[i, j] = Int32.MinValue;
dp[0, 0] = Math.Max(0, arr[0]);
dp[0, 1] = -1 * arr[0];
for (int i = 1; i < n; ++i) {
// dp[i][0] represents sum till ith index
// without inverting any element.
dp[i, 0]
= Math.Max(arr[i], dp[i - 1, 0] + arr[i]);
// dp[i][1] represents sum till ith index
// after inverting one element.
dp[i, 1] = Math.Max(0, dp[i - 1, 0]) - arr[i];
if (i >= 1) {
dp[i, 1] = Math.Max(dp[i, 1],
dp[i - 1, 1] + arr[i]);
// dp[i][2] represents sum till ith index
// after inverting two elements.
dp[i, 2] = dp[i - 1, 1] - arr[i];
}
if (i >= 2) {
dp[i, 2] = Math.Max(dp[i, 2],
dp[i - 1, 2] + arr[i]);
}
maxSum = Math.Max(maxSum, dp[i, 0]);
maxSum = Math.Max(maxSum, dp[i, 1]);
maxSum = Math.Max(maxSum, dp[i, 2]);
}
return maxSum;
}
// Driver Code
public static void Main()
{
int n = 8;
int[] A = { 2, -1, -18, 3, -1, -39, 5, -2 };
// vector 'arr' contains sum of consecutive
// positive or negative elements.
List<int> arr = new List<int>();
mergeElements(n, arr, A);
Console.WriteLine(findMaxSum(arr, arr.Count));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to merge alternate elements into groups
// of positive and negative
function mergeElements(n, arr, A) {
let i = 0;
let sum = 0;
while (i < n) {
sum = 0;
while (i < n && A[i] >= 0) {
sum += A[i];
i++;
}
if (sum > 0) {
arr.push(sum);
}
sum = 0;
while (i < n && A[i] < 0) {
sum += A[i];
i++;
}
if (sum < 0) {
arr.push(sum);
}
}
}
// Function to return the maximum
// after inverting at most 2 elements
function findMaxSum(arr, n) {
let maxSum = 0;
let dp = new Array(n);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(3).fill(Number.MIN_VALUE);
}
dp[0][0] = Math.max(0, arr[0]);
dp[0][1] = -1 * arr[0];
for (let i = 1; i < n; ++i) {
// dp[i][0] represents sum till ith index
// without inverting any element.
dp[i][0] = Math.max(arr[i],
dp[i - 1][0] + arr[i]);
// dp[i][1] represents sum till ith index
// after inverting one element.
dp[i][1] = Math.max(0, dp[i - 1][0]) - arr[i];
if (i >= 1) {
dp[i][1] = Math.max(dp[i][1],
dp[i - 1][1] + arr[i]);
// dp[i][2] represents sum till ith index
// after inverting two elements.
dp[i][2] = dp[i - 1][1] - arr[i];
}
if (i >= 2) {
dp[i][2] = Math.max(dp[i][2],
dp[i - 1][2] + arr[i]);
}
maxSum = Math.max(maxSum, dp[i][0]);
maxSum = Math.max(maxSum, dp[i][1]);
maxSum = Math.max(maxSum, dp[i][2]);
}
return maxSum;
}
// Driver Code
let n = 8;
let A = [2, -1, -18, 3, -1, -39, 5, -2];
// vector 'arr' contains sum of consecutive
// positive or negative elements.
let arr = [];
mergeElements(n, arr, A);
document.write(findMaxSum(arr, arr.length));
// This code is contributed by Potta Lokesh
</script>
Producción
69
Complejidad temporal : O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA