Subarreglo de suma máxima de longitud par

Dada una array arr[] de N elementos, la tarea es encontrar la suma máxima de cualquier subarreglo de longitud X tal que X > 0 y X % 2 = 0 .
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3} 
Salida: 5 
{2, 3} es el subarreglo requerido.
Entrada: arr[] = {8, 9, -8, 9, 10} 
Salida: 20 
{9, -8, 9, 10} es el subarreglo requerido. 
Aunque {8, 9, -8, 9, 10} tiene la suma máxima 
pero no tiene la misma longitud. 
 

Enfoque: Este problema es una variación del problema de la suma máxima de subarreglos y se puede resolver utilizando el enfoque de programación dinámica . Cree un arreglo dp[] donde dp[i] almacenará la suma máxima de un subarreglo de longitud par cuyo primer elemento sea arr[i] . Ahora la relación de recurrencia será: 
 

dp[i] = max((arr[i] + arr[i + 1]), (arr[i] + arr[i + 1] + dp[i + 2]))

 
Esto se debe a que el subarreglo de longitud par de suma máxima que comienza con el elemento arr[i] puede ser la suma de arr[i] y arr[i + 1] o puede ser arr[i] + arr[i + 1] agregado con la suma máxima del subarreglo de longitud par que comienza con arr[i + 2], es decir , dp[i + 2] . Tome el máximo de estos dos. 
Al final, el valor máximo de la array dp[] será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum
// subarray sum of even length
int maxEvenLenSum(int arr[], int n)
{
 
    // There has to be at
    // least 2 elements
    if (n < 2)
        return 0;
 
    // dp[i] will store the maximum
    // subarray sum of even length
    // starting at arr[i]
    int dp[n] = { 0 };
 
    // Valid subarray cannot start from
    // the last element as its
    // length has to be even
    dp[n - 1] = 0;
    dp[n - 2] = arr[n - 2] + arr[n - 1];
 
    for (int i = n - 3; i >= 0; i--) {
 
        // arr[i] and arr[i + 1] can be added
        // to get an even length subarray
        // starting at arr[i]
        dp[i] = arr[i] + arr[i + 1];
 
        // If the sum of the valid subarray starting
        // from arr[i + 2] is greater than 0 then it
        // can be added with arr[i] and arr[i + 1]
        // to maximize the sum of the subarray
        // starting from arr[i]
        if (dp[i + 2] > 0)
            dp[i] += dp[i + 2];
    }
 
    // Get the sum of the even length
    // subarray with maximum sum
    int maxSum = *max_element(dp, dp + n);
    return maxSum;
}
 
// Driver code
int main()
{
 
    int arr[] = { 8, 9, -8, 9, 10 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << maxEvenLenSum(arr, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.Arrays;
 
class GFG
{
 
// Function to return the maximum
// subarray sum of even length
static int maxEvenLenSum(int arr[], int n)
{
 
    // There has to be at
    // least 2 elements
    if (n < 2)
        return 0;
 
    // dp[i] will store the maximum
    // subarray sum of even length
    // starting at arr[i]
    int []dp = new int[n];
 
    // Valid subarray cannot start from
    // the last element as its
    // length has to be even
    dp[n - 1] = 0;
    dp[n - 2] = arr[n - 2] + arr[n - 1];
 
    for (int i = n - 3; i >= 0; i--)
    {
 
        // arr[i] and arr[i + 1] can be added
        // to get an even length subarray
        // starting at arr[i]
        dp[i] = arr[i] + arr[i + 1];
 
        // If the sum of the valid subarray starting
        // from arr[i + 2] is greater than 0 then it
        // can be added with arr[i] and arr[i + 1]
        // to maximize the sum of the subarray
        // starting from arr[i]
        if (dp[i + 2] > 0)
            dp[i] += dp[i + 2];
    }
 
    // Get the sum of the even length
    // subarray with maximum sum
    int maxSum = Arrays.stream(dp).max().getAsInt();
    return maxSum;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 8, 9, -8, 9, 10 };
    int n = arr.length;
 
    System.out.println(maxEvenLenSum(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to return the maximum
# subarray sum of even length
def maxEvenLenSum(arr, n):
 
    # There has to be at
    # least 2 elements
    if (n < 2):
        return 0
 
    # dp[i] will store the maximum
    # subarray sum of even length
    # starting at arr[i]
    dp = [0 for i in range(n)]
 
    # Valid subarray cannot start from
    # the last element as its
    # length has to be even
    dp[n - 1] = 0
    dp[n - 2] = arr[n - 2] + arr[n - 1]
 
    for i in range(n - 3, -1, -1):
 
        # arr[i] and arr[i + 1] can be added
        # to get an even length subarray
        # starting at arr[i]
        dp[i] = arr[i] + arr[i + 1]
 
        # If the sum of the valid subarray
        # starting from arr[i + 2] is
        # greater than 0 then it can be added
        # with arr[i] and arr[i + 1]
        # to maximize the sum of the
        # subarray starting from arr[i]
        if (dp[i + 2] > 0):
            dp[i] += dp[i + 2]
 
    # Get the sum of the even length
    # subarray with maximum sum
    maxSum = max(dp)
    return maxSum
 
# Driver code
arr = [8, 9, -8, 9, 10]
n = len(arr)
 
print(maxEvenLenSum(arr, n))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
    static int MaxSum(int []arr)
    {
          
        // assigning first element to the array
        int large = arr[0];
         
        // loop to compare value of large
        // with other elements
        for (int i = 1; i < arr.Length; i++)
        {
            // if large is smaller than other element
            // assign that element to the large
            if (large < arr[i])
                large = arr[i];
        }
        return large;
    }
     
    // Function to return the maximum
    // subarray sum of even length
    static int maxEvenLenSum(int []arr, int n)
    {
     
        // There has to be at
        // least 2 elements
        if (n < 2)
            return 0;
     
        // dp[i] will store the maximum
        // subarray sum of even length
        // starting at arr[i]
        int []dp = new int[n];
     
        // Valid subarray cannot start from
        // the last element as its
        // length has to be even
        dp[n - 1] = 0;
        dp[n - 2] = arr[n - 2] + arr[n - 1];
     
        for (int i = n - 3; i >= 0; i--)
        {
     
            // arr[i] and arr[i + 1] can be added
            // to get an even length subarray
            // starting at arr[i]
            dp[i] = arr[i] + arr[i + 1];
     
            // If the sum of the valid subarray starting
            // from arr[i + 2] is greater than 0 then it
            // can be added with arr[i] and arr[i + 1]
            // to maximize the sum of the subarray
            // starting from arr[i]
            if (dp[i + 2] > 0)
                dp[i] += dp[i + 2];
        }
     
        // Get the sum of the even length
        // subarray with maximum sum
        int maxSum = MaxSum(dp);
        return maxSum;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { 8, 9, -8, 9, 10 };
        int n = arr.Length;
     
        Console.WriteLine(maxEvenLenSum(arr, n));
    }
}
 
// This code is contributed by kanugargng

<script>
// Javascript implementation of the approach
 
// Function to return the maximum
// subarray sum of even length
function maxEvenLenSum(arr, n) {
 
    // There has to be at
    // least 2 elements
    if (n < 2)
        return 0;
 
    // dp[i] will store the maximum
    // subarray sum of even length
    // starting at arr[i]
    let dp = new Array(n).fill(0);
 
    // Valid subarray cannot start from
    // the last element as its
    // length has to be even
    dp[n - 1] = 0;
    dp[n - 2] = arr[n - 2] + arr[n - 1];
 
    for (let i = n - 3; i >= 0; i--) {
 
        // arr[i] and arr[i + 1] can be added
        // to get an even length subarray
        // starting at arr[i]
        dp[i] = arr[i] + arr[i + 1];
 
        // If the sum of the valid subarray starting
        // from arr[i + 2] is greater than 0 then it
        // can be added with arr[i] and arr[i + 1]
        // to maximize the sum of the subarray
        // starting from arr[i]
        if (dp[i + 2] > 0)
            dp[i] += dp[i + 2];
    }
 
    // Get the sum of the even length
    // subarray with maximum sum
    let maxSum = dp.sort((a, b) => b - a)[0];
    return maxSum;
}
 
// Driver code
let arr = [8, 9, -8, 9, 10];
let n = arr.length;
 
document.write(maxEvenLenSum(arr, n));
 
// This code is contributed by _saurabh_jaiswal.
</script>

20

Complejidad temporal: O(n) 
Complejidad espacial: O(n)