Dada una array arr[] de N enteros y un entero K , la tarea es encontrar la suma máxima de la sub-array cambiando los signos de como máximo K elementos de la array.
Ejemplos:
Entrada: arr[] = {-6, 2, -1, -1000, 2}, k = 2
Salida: 1009
Podemos invertir los signos de -6 y -1000, para obtener la suma máxima de subarreglo como 1009Entrada: arr[] = {-1, -2, -100, -10}, k = 1
Salida: 100
Solo podemos invertir el signo de -100 para obtener 100Entrada: {1, 2, 100, 10}, k = 1
Salida: 113
No necesitamos voltear ningún elemento
Planteamiento: El problema se puede resolver usando Programación Dinámica . Sea dp[i][j] la suma máxima del subconjunto del índice i con j flips. Se puede escribir una función recursiva para resolver el problema y podemos usar la memorización para evitar múltiples llamadas a funciones. La función DP recursiva (findSubarraySum(ind, flips)) se llamará desde cada índice con el número de giros iniciales como 0.
ans = max(0, a[ind] + findSubarraySum(ind + 1, voltea, n, a, k))
ans = max(ans, -a[ind] + findSubarraySum(ind + 1, voltea + 1, n, a, k))
Si el valor es negativo, lo reemplazamos por 0, de manera similar a como lo hacemos en el algoritmo de Kadane.
La función recursiva tendrá dos estados, uno será si volteamos el i-ésimo índice. La segunda es si no volteamos el i-ésimo índice. Los casos base son si el ind==n cuando hemos completado un recorrido hasta el último índice. Podemos usar la memorización para almacenar los resultados que se pueden usar más tarde para evitar múltiples llamadas a la misma función. El máximo de todos los dp[i][0] será nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int dp[left][right];
// Function to find the maximum subarray sum with flips
// starting from index i
int findSubarraySum(int ind, int flips, int n, int a[],
int k)
{
// If the number of flips have exceeded
if (flips > k)
return -1e9;
// Complete traversal
if (ind == n)
return 0;
// If the state has previously been visited
if (dp[ind][flips] != -1)
return dp[ind][flips];
// Initially
int ans = 0;
// Use Kadane's algorithm and call two states
ans = max(
0,
a[ind] + findSubarraySum(ind + 1, flips, n, a, k));
ans = max(ans, -a[ind]
+ findSubarraySum(ind + 1, flips + 1,
n, a, k));
// Memoize the answer and return it
return dp[ind][flips] = ans;
}
// Utility function to call flips from index and
// return the answer
int findMaxSubarraySum(int a[], int n, int k)
{
// Create DP array
// int dp[n][k+1];
memset(dp, -1, sizeof(dp));
int ans = -1e9;
// Iterate and call recursive function
// from every index to get the maximum subarray sum
for (int i = 0; i < n; i++)
ans = max(ans, findSubarraySum(i, 0, n, a, k));
// corner case
if (ans == 0 && k == 0)
return *max_element(a, a + n);
return ans;
}
// Driver Code
int main()
{
int a[] = { -1, -2, -100, -10 };
int n = sizeof(a) / sizeof(a[0]);
int k = 1;
cout << findMaxSubarraySum(a, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG {
static int right = 2;
static int left = 4;
static int[][] dp = new int[left][right];
// Function to find the maximum subarray sum with flips
// starting from index i
static int findSubarraySum(int ind, int flips, int n,
int[] a, int k)
{
// If the number of flips have exceeded
if (flips > k)
return (int)(-1e9);
// Complete traversal
if (ind == n)
return 0;
// If the state has previously been visited
if (dp[ind][flips] != -1)
return dp[ind][flips];
// Initially
int ans = 0;
// Use Kadane's algorithm and call two states
ans = Math.max(0, a[ind]
+ findSubarraySum(
ind + 1, flips, n, a, k));
ans = Math.max(ans, -a[ind]
+ findSubarraySum(ind + 1,
flips + 1,
n, a, k));
// Memoize the answer and return it
return dp[ind][flips] = ans;
}
// Utility function to call flips from index and
// return the answer
static int findMaxSubarraySum(int[] a, int n, int k)
{
// Create DP array
// int dp[n,k+1];
for (int i = 0; i < n; i++)
for (int j = 0; j < k + 1; j++)
dp[i][j] = -1;
int ans = (int)(-1e9);
// Iterate and call recursive function
// from every index to get the maximum subarray sum
for (int i = 0; i < n; i++)
ans = Math.max(ans,
findSubarraySum(i, 0, n, a, k));
// corner case
if (ans == 0 && k == 0)
return Arrays.stream(a).max().getAsInt();
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] a = { -1, -2, -100, -10 };
int n = a.length;
int k = 1;
System.out.println(findMaxSubarraySum(a, n, k));
}
}
// This code is contributed by mits
Python3
# Python3 implementation of the approach import numpy as np right = 3; left = 6; dp = np.ones((left, right)) dp = -1 * dp # Function to find the maximum # subarray sum with flips starting # from index i def findSubarraySum(ind, flips, n, a, k) : # If the number of flips # have exceeded if (flips > k) : return -1e9; # Complete traversal if (ind == n) : return 0; # If the state has previously # been visited if (dp[ind][flips] != -1) : return dp[ind][flips]; # Initially ans = 0; # Use Kadane's algorithm and # call two states ans = max(0, a[ind] + findSubarraySum(ind + 1, flips, n, a, k)); ans = max(ans, -a[ind] + findSubarraySum(ind + 1, flips + 1, n, a, k)); # Memoize the answer and return it dp[ind][flips] = ans; return dp[ind][flips] ; # Utility function to call flips # from index and return the answer def findMaxSubarraySum(a, n, k) : ans = -1e9; # Iterate and call recursive # function from every index to # get the maximum subarray sum for i in range(n) : ans = max(ans, findSubarraySum(i, 0, n, a, k)); # corner casae if ans == 0 and k == 0: return max(a); return ans; # Driver Code if __name__ == "__main__" : a = [-1, -2, -100, -10]; n = len(a) ; k = 1; print(findMaxSubarraySum(a, n, k)); # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
using System.Linq;
class GFG {
static int right = 2;
static int left = 4;
static int[, ] dp = new int[left + 1, right + 1];
// Function to find the maximum subarray sum
// with flips starting from index i
static int findSubarraySum(int ind, int flips, int n,
int[] a, int k)
{
// If the number of flips have exceeded
if (flips > k)
return -(int)1e9;
// Complete traversal
if (ind == n)
return 0;
// If the state has previously been visited
if (dp[ind, flips] != -1)
return dp[ind, flips];
// Initially
int ans = 0;
// Use Kadane's algorithm and call two states
ans = Math.Max(0, a[ind]
+ findSubarraySum(
ind + 1, flips, n, a, k));
ans = Math.Max(ans, -a[ind]
+ findSubarraySum(ind + 1,
flips + 1,
n, a, k));
// Memoize the answer and return it
return dp[ind, flips] = ans;
}
// Utility function to call flips from
// index and return the answer
static int findMaxSubarraySum(int[] a, int n, int k)
{
// Create DP array
// int dp[n][k+1];
for (int i = 0; i < n; i++)
for (int j = 0; j < k + 1; j++)
dp[i, j] = -1;
int ans = -(int)1e9;
// Iterate and call recursive function
// from every index to get the maximum subarray sum
for (int i = 0; i < n; i++)
ans = Math.Max(ans,
findSubarraySum(i, 0, n, a, k));
// corner case
if (ans == 0 && k == 0)
return a.Max();
return ans;
}
// Driver Code
static void Main()
{
int[] a = { -1, -2, -100, -10 };
int n = a.Length;
int k = 1;
Console.WriteLine(findMaxSubarraySum(a, n, k));
}
}
// This code is contributed by mits
Javascript
<script>
// Javascript implementation of the approach
let right = 2;
let left = 4;
let dp = new Array(left);
// Function to find the maximum subarray sum with flips
// starting from index i
function findSubarraySum(ind, flips, n, a, k)
{
// If the number of flips have exceeded
if (flips > k)
return (-1e9);
// Complete traversal
if (ind == n)
return 0;
// If the state has previously been visited
if (dp[ind][flips] != -1)
return dp[ind][flips];
// Initially
let ans = 0;
// Use Kadane's algorithm and call two states
ans = Math.max(0, a[ind]
+ findSubarraySum(
ind + 1, flips, n, a, k));
ans = Math.max(ans, -a[ind]
+ findSubarraySum(ind + 1,
flips + 1,
n, a, k));
// Memoize the answer and return it
return dp[ind][flips] = ans;
}
// Utility function to call flips from index and
// return the answer
function findMaxSubarraySum(a, n, k)
{
// Create DP array
// int dp[n,k+1];
for (let i = 0; i < n; i++)
{
dp[i] = new Array(k);
for (let j = 0; j < k + 1; j++)
{
dp[i][j] = -1;
}
}
let ans = (-1e9);
// Iterate and call recursive function
// from every index to get the maximum subarray sum
for (let i = 0; i < n; i++)
ans = Math.max(ans,
findSubarraySum(i, 0, n, a, k));
// corner case
if (ans == 0 && k == 0)
{
let max = Number.MIN_VALUE;
for(let i = 0; i < a.length; i++)
{
max = Math.max(max, a[i]);
}
return max;
}
return ans;
}
let a = [ -1, -2, -100, -10 ];
let n = a.length;
let k = 1;
document.write(findMaxSubarraySum(a, n, k));
</script>
100
Complejidad de tiempo: O (N * K), ya que estamos usando un bucle para atravesar N veces y llamamos recursivamente a la función K veces, lo que costará O (K). Donde N es el número de elementos en la array y K es el límite de elementos.
Espacio Auxiliar: O(N * K), ya que estamos usando espacio extra para la memorización. Donde N es el número de elementos en la array y K es el límite de elementos.