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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por coder_maddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA