Suma máxima de dos subarreglos no superpuestos de cualquier longitud

Dada una array A que consta de N enteros, la tarea es encontrar la suma máxima de dos subarreglos que no se superponen de cualquier longitud de la array.

Nota: También puede seleccionar subarreglos vacíos.

Ejemplos: 

Entrada: N =3, A[] = {-4, -5, -2}
Salida: 0
Explicación: dos subarreglos vacíos son óptimos con suma máxima = 0.

Entrada:   N =5, A[] = {5, -2, 3, -6, 5}
Salida: 11
Explicación: Los subarreglos óptimos son {5, -2, 3} y {5} con suma máxima = 11.

Acercarse:Para resolver el problema, siga la siguiente idea:

Este problema se puede considerar como el subarreglo contiguo de suma máxima (algoritmo de Kadane) desde las direcciones izquierda y derecha. 
Al aplicar este algoritmo, estamos asegurando una suma contigua máxima hasta un índice que se puede almacenar en dos vectores desde el frente y el reverso para encontrar la suma máxima que no se interseca .

Siga los pasos dados para resolver el problema:

• Inicialice dos vectores frontKadane y backKadane con 0 .
• Atraviese el arreglo A e implemente el Algoritmo de Kadane de izquierda a derecha y almacene la suma máxima del subarreglo en frontKadane[i] .
• Atraviese el arreglo A e implemente el algoritmo Kadane de derecha a izquierda y almacene la suma máxima del subarreglo en backKadane[i] .
• Atraviese de 0 a N y calcule el valor máximo de (frontKadane[i] + backKadane[i]) y guárdelo en la variable result .
• Devuelve los resultados como la respuesta final. 

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

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// Function to find the maximum sum
// of two non-overlapping subarray
int maxNonIntersectSum(int* A, int& N)
{
    vector<int> frontKadane;
    vector<int> backKadane(N);
    int sum1 = 0, sum2 = 0, result = 0;
 
    frontKadane.push_back(0);
    backKadane.push_back(0);
 
    // Loop to calculate the
    // maximum subarray sum till ith index
    for (int i = 0; i < N; i++) {
        sum1 += A[i];
        sum2 = max(sum1, sum2);
        sum1 = max(sum1, 0);
        frontKadane.push_back(sum2);
    }
 
    sum1 = 0;
    sum2 = 0;
 
    // Loop to calculate the
    // maximum subarray sum till ith index
    for (int i = N - 1; i >= 0; i--) {
        sum1 += A[i];
        sum2 = max(sum1, sum2);
        sum1 = max(sum1, 0);
        backKadane[i] = sum2;
    }
 
    for (int i = 0; i <= N; i++)
        result
            = max(result, backKadane[i]
                              + frontKadane[i]);
 
    // Return the maximum
    // non-overlapping subarray sum
    return result;
}
 
// Driver code
int main()
{
    int A[] = { 5, -2, 3, -6, 5 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << maxNonIntersectSum(A, N);
    return 0;
}

// Java code for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the maximum sum of two
    // non-overlapping subarray
    static int maxNonIntersect(int[] A, int N)
    {
 
        int[] frontKadane = new int[N];
        int[] backKadane = new int[N];
 
        int sum1 = 0, sum2 = 0, result = 0;
 
        // Loop to calculate the maximum subarray sum till
        // ith index
        for (int i = 0; i < N; i++) {
            sum1 += A[i];
            sum2 = Math.max(sum1, sum2);
            sum1 = Math.max(sum1, 0);
            frontKadane[i] = sum2;
        }
 
        sum1 = 0;
        sum2 = 0;
 
        // Loop to calculate the maximum subarray sum till
        // ith index
        for (int i = N - 1; i >= 0; i--) {
            sum1 += A[i];
            sum2 = Math.max(sum1, sum2);
            sum1 = Math.max(sum1, 0);
            backKadane[i] = sum2;
        }
 
        for (int i = 0; i < N; i++) {
            result = Math.max(result, backKadane[i]
                                          + frontKadane[i]);
        }
 
        // Return the maximum non-overlapping subarray sum
        return result;
    }
 
    public static void main(String[] args)
    {
 
        int[] A = { 5, -2, 3, -6, 5 };
        int N = A.length;
 
        // Function call
        System.out.print(maxNonIntersect(A, N));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

// C# code for the above approach
 
using System;
 
public class GFG {
 
    // Function to find the maximum sum of two
    // non-overlapping subarray
    static int maxNonIntersect(int[] A, int N)
    {
 
        int[] frontKadane = new int[N];
        int[] backKadane = new int[N];
 
        int sum1 = 0, sum2 = 0, result = 0;
 
        // Loop to calculate the maximum subarray sum till
        // ith index
        for (int i = 0; i < N; i++) {
            sum1 += A[i];
            sum2 = Math.Max(sum1, sum2);
            sum1 = Math.Max(sum1, 0);
            frontKadane[i] = sum2;
        }
 
        sum1 = 0;
        sum2 = 0;
 
        // Loop to calculate the maximum subarray sum till
        // ith index
        for (int i = N - 1; i >= 0; i--) {
            sum1 += A[i];
            sum2 = Math.Max(sum1, sum2);
            sum1 = Math.Max(sum1, 0);
            backKadane[i] = sum2;
        }
 
        for (int i = 0; i < N; i++) {
            result = Math.Max(result, backKadane[i]
                                          + frontKadane[i]);
        }
 
        // Return the maximum non-overlapping subarray sum
        return result;
    }
 
    public static void Main(string[] args)
    {
 
        int[] A = { 5, -2, 3, -6, 5 };
        int N = A.Length;
 
        // Function call
        Console.Write(maxNonIntersect(A, N));
    }
}
 
// This code is contributed by AnkThon

11

Complejidad temporal: O(N)
Espacio auxiliar: O(N)