Calcule el máximo de la función de manera eficiente en todos los subconjuntos

Posted on by Rudeus Greyrat

Dada una array, arr[] y una función F(i, j) . La tarea es calcular max{F(i, j)} sobre todos los sub-arreglos [i..j].
La función F() se define como: 

F(l, r) = \sum_{i = l}^{r - 1} |arr[i] - arr[i+1]|.(-1)^{i-l}

Ejemplos: 

Entrada: array[] = { 1, 5, 4, 7 } 
Salida: 6 
Valores de F(i, j) para todas las sub-arrays: 
{ 1, 5 } = |1 – 5| * (1) = 4 
{ 1, 5, 4 } = |1 – 5| * (1) + |5 – 4| * (-1) = 3 
{ 1, 5, 4, 7 } = |1 – 5| * (1) + |5 – 4| * (-1) + |4 – 7| * (1) = 6 
{ 5, 4 } = |5 – 4| * (1) = 1 
{ 5, 4, 7 } = |5 – 4| * (1) + |4 – 7| * (-1) = -2 
{ 4, 7 } = |4 – 7| * (1) = 3
Max de todos los valores anteriores = 6. 

Entrada: arr[] = { 1, 4, 2, 3, 1 } 
Salida: 3 
 

Enfoque ingenuo : un enfoque ingenuo es recorrer todos los subconjuntos y calcular el máximo de la función F sobre todos los subconjuntos.

Enfoque eficiente : un mejor enfoque es considerar segmentos en F(l, r) con l par e impar por separado. Se pueden construir dos arrays diferentes B[] y C[] para este propósito, de modo que:  

B[i] = |arr[i] - arr[i + 1]| * (-1)i
C[i] = |arr[i] - arr[i + 1]| * (-1)i + 1

Ahora, si observamos de cerca, solo necesitamos encontrar el subarreglo de suma máxima de los arreglos B[] y C[] y la respuesta final de la función será el máximo entre ambos arreglos.

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

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
 
#define MAX 100005
 
using namespace std;
 
// Function to return maximum sum of a sub-array
int kadaneAlgorithm(const int* ar, int n)
{
    int sum = 0, maxSum = 0;
 
    for (int i = 0; i < n; i++) {
 
        sum += ar[i];
 
        if (sum < 0)
            sum = 0;
 
        maxSum = max(maxSum, sum);
    }
 
    return maxSum;
}
 
// Function to return maximum value of function F
int maxFunction(const int* arr, int n)
{
 
    int b[MAX], c[MAX];
 
    // Compute arrays B[] and C[]
    for (int i = 0; i < n - 1; i++) {
        if (i & 1) {
            b[i] = abs(arr[i + 1] - arr[i]);
            c[i] = -b[i];
        }
        else {
            c[i] = abs(arr[i + 1] - arr[i]);
            b[i] = -c[i];
        }
    }
 
    // Find maximum sum sub-array of both of the
    // arrays and take maximum among them
    int ans = kadaneAlgorithm(b, n - 1);
    ans = max(ans, kadaneAlgorithm(c, n - 1));
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 5, 4, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxFunction(arr, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static int MAX = 100005;
 
 
// Function to return maximum sum of a sub-array
static int kadaneAlgorithm(int[] ar, int n)
{
    int sum = 0, maxSum = 0;
 
    for (int i = 0; i < n; i++)
    {
        sum += ar[i];
 
        if (sum < 0)
            sum = 0;
 
        maxSum = Math.max(maxSum, sum);
    }
 
    return maxSum;
}
 
// Function to return maximum value
// of function F
static int maxFunction(int[] arr, int n)
{
 
    int []b = new int[MAX];
    int []c = new int[MAX];
 
    // Compute arrays B[] and C[]
    for (int i = 0; i < n - 1; i++)
    {
        if (i % 2 == 1)
        {
            b[i] = Math.abs(arr[i + 1] - arr[i]);
            c[i] = -b[i];
        }
        else
        {
            c[i] = Math.abs(arr[i + 1] - arr[i]);
            b[i] = -c[i];
        }
    }
 
    // Find maximum sum sub-array of both of the
    // arrays and take maximum among them
    int ans = kadaneAlgorithm(b, n - 1);
    ans = Math.max(ans, kadaneAlgorithm(c, n - 1));
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 5, 4, 7 };
    int n = arr.length;
    System.out.println(maxFunction(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the above approach
MAX = 100005;
 
# Function to return maximum
# sum of a sub-array
def kadaneAlgorithm(ar, n) :
 
    sum = 0; maxSum = 0;
 
    for i in range(n) :
 
        sum += ar[i];
 
        if (sum < 0) :
            sum = 0;
 
        maxSum = max(maxSum, sum);
 
    return maxSum;
 
# Function to return maximum
# value of function F
def maxFunction(arr, n) :
 
    b = [0] * MAX;
    c = [0] * MAX;
 
    # Compute arrays B[] and C[]
    for i in range(n - 1) :
        if (i & 1) :
            b[i] = abs(arr[i + 1] - arr[i]);
            c[i] = -b[i];
         
        else :
            c[i] = abs(arr[i + 1] - arr[i]);
            b[i] = -c[i];
 
    # Find maximum sum sub-array of both of the
    # arrays and take maximum among them
    ans = kadaneAlgorithm(b, n - 1);
    ans = max(ans, kadaneAlgorithm(c, n - 1));
 
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 5, 4, 7 ];
    n = len(arr)
 
    print(maxFunction(arr, n));
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
     
class GFG
{
static int MAX = 100005;
 
// Function to return maximum sum of a sub-array
static int kadaneAlgorithm(int[] ar, int n)
{
    int sum = 0, maxSum = 0;
 
    for (int i = 0; i < n; i++)
    {
        sum += ar[i];
 
        if (sum < 0)
            sum = 0;
 
        maxSum = Math.Max(maxSum, sum);
    }
 
    return maxSum;
}
 
// Function to return maximum value
// of function F
static int maxFunction(int[] arr, int n)
{
    int []b = new int[MAX];
    int []c = new int[MAX];
 
    // Compute arrays B[] and C[]
    for (int i = 0; i < n - 1; i++)
    {
        if (i % 2 == 1)
        {
            b[i] = Math.Abs(arr[i + 1] - arr[i]);
            c[i] = -b[i];
        }
        else
        {
            c[i] = Math.Abs(arr[i + 1] - arr[i]);
            b[i] = -c[i];
        }
    }
 
    // Find maximum sum sub-array of both of the
    // arrays and take maximum among them
    int ans = kadaneAlgorithm(b, n - 1);
    ans = Math.Max(ans, kadaneAlgorithm(c, n - 1));
 
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 5, 4, 7 };
    int n = arr.Length;
    Console.WriteLine(maxFunction(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript implementation of the above approach
const MAX = 100005;
 
// Function to return maximum sum of a sub-array
function kadaneAlgorithm(ar, n)
{
    let sum = 0, maxSum = 0;
 
    for(let i = 0; i < n; i++)
    {
        sum += ar[i];
 
        if (sum < 0)
            sum = 0;
 
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}
 
// Function to return maximum
// value of function F
function maxFunction(arr, n)
{
    let b = new Array(MAX),
        c = new Array(MAX);
 
    // Compute arrays B[] and C[]
    for(let i = 0; i < n - 1; i++)
    {
        if (i & 1)
        {
            b[i] = Math.abs(arr[i + 1] -
                            arr[i]);
            c[i] = -b[i];
        }
        else
        {
            c[i] = Math.abs(arr[i + 1] -
                            arr[i]);
            b[i] = -c[i];
        }
    }
 
    // Find maximum sum sub-array of both of the
    // arrays and take maximum among them
    let ans = kadaneAlgorithm(b, n - 1);
    ans = Math.max(ans,
          kadaneAlgorithm(c, n - 1));
 
    return ans;
}
 
// Driver code
let arr = [ 1, 5, 4, 7 ];
let n = arr.length;
 
document.write(maxFunction(arr, n));
 
// This code is contributed by Manoj.
 
</script>
Producción: 

6

 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(MAX)

Publicación traducida automáticamente

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