Suma máxima de subarreglo cambiando los signos de como máximo K elementos del arreglo

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 1009

Entrada: arr[] = {-1, -2, -100, -10}, k = 1
Salida: 100
Solo podemos invertir el signo de -100 para obtener 100

Entrada: {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>

Producción

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.

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta