Given an array arr[] of N elements, the task is to find the maximum sum of any subarray of length X such that X > 0 and X % 2 = 0.
Examples:
Input: arr[] = {1, 2, 3}
Output: 5
{2, 3} is the required subarray.
Input: arr[] = {8, 9, -8, 9, 10}
Output: 20
{9, -8, 9, 10} is the required subarray.
Even though {8, 9, -8, 9, 10} has the maximum sum
but it is not of even length.
Approach: This problem is a variation of maximum subarray sum problem and can be solved using dynamic programming approach. Create an array dp[] where dp[i] will store the maximum sum of an even length subarray whose first element is arr[i]. Now the recurrence relation will be:
dp[i] = max((arr[i] + arr[i + 1]), (arr[i] + arr[i + 1] + dp[i + 2]))
This is because the maximum sum even length subarray starting with the element arr[i] can either be the sum of arr[i] and arr[i + 1] or it can be arr[i] + arr[i + 1] added with the maximum sum of even length subarray starting with arr[i + 2] i.e. dp[i + 2]. Take the maximum of these two.
In the end, the maximum value from the dp[] array will be the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum// subarray sum of even lengthint 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 codeint 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 approachimport java.util.Arrays;class GFG {// Function to return the maximum// subarray sum of even lengthstatic 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 codepublic 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 lengthdef 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 codearr = [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 lengthfunction 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 codelet arr = [8, 9, -8, 9, 10];let n = arr.length;document.write(maxEvenLenSum(arr, n));// This code is contributed by _saurabh_jaiswal.</script> |
Output
20
Time complexity: O(n)
Space complexity: O(n)
Efficient approach : Space optimization O(1)
To optimize the space complexity of previous approach we using only two variables to keep track of the previous two subproblems instead of creating an array of size n to store all the subproblem solutions. This way, we can reduce the space complexity from O(n) to O(1).
Implementation Steps:
- Check if the array size is less than 2, return 0 if true.
- Initialize prevPrevSum to 0 and prevSum to arr[n-2] + arr[n-1], which represents the sum of the last two elements of the array.
- Traverse the array from the second-last index to the first index and compute the sum of every even length subarray that ends at the current index.
- Add the current element and the next element of the array to get the sum of the current even-length subarray.
- If the sum of the subarray two indices ahead is greater than 0, add it to the current subarray sum.
- Update prevPrevSum and prevSum with the previous subarray sums for further iterations.
- At last Return the maximum of prevSum and prevPrevSum.
Implementation:
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std; int maxEvenLenSum(int arr[], int n){ // There has to be at // least 2 elements if (n < 2) return 0; // initialize variables to store the previous values int prevPrevSum = 0, prevSum = arr[n - 2] + arr[n - 1], currSum; // iterate over subproblems and get the current value from previous computations for (int i = n - 3; i >= 0; i--) { currSum = arr[i] + arr[i + 1]; if (prevPrevSum > 0) currSum += prevPrevSum; // assigning values for further iterations prevPrevSum = prevSum; prevSum = currSum; } // return answer return max(prevSum, prevPrevSum);}// Driver codeint main(){ int arr[] = { 8, 9, -8, 9, 10 }; int n = sizeof(arr) / sizeof(int); // function call cout << maxEvenLenSum(arr, n); return 0;} |
Java
// Java code for above approachimport java.util.*;public class Main { static int maxEvenLenSum(int arr[], int n) { // There has to be at // least 2 elements if (n < 2) return 0; // initialize variables to store the previous values int prevPrevSum = 0, prevSum = arr[n - 2] + arr[n - 1], currSum; // iterate over subproblems and get the current value from previous computations for (int i = n - 3; i >= 0; i--) { currSum = arr[i] + arr[i + 1]; if (prevPrevSum > 0) currSum += prevPrevSum; // assigning values for further iterations prevPrevSum = prevSum; prevSum = currSum; } // return answer return Math.max(prevSum, prevPrevSum); } // Driver code public static void main(String[] args) { int arr[] = { 8, 9, -8, 9, 10 }; int n = arr.length; // function call System.out.println(maxEvenLenSum(arr, n)); } } |
Python3
def maxEvenLenSum(arr, n): # There has to be at least 2 elements if n < 2: return 0 # initialize variables to store the previous values prevPrevSum = 0 prevSum = arr[n - 2] + arr[n - 1] # iterate over subproblems and get the current value from previous computations for i in range(n - 3, -1, -1): currSum = arr[i] + arr[i + 1] if prevPrevSum > 0: currSum += prevPrevSum # assigning values for further iterations prevPrevSum = prevSum prevSum = currSum # return answer return max(prevSum, prevPrevSum)# Driver codearr = [8, 9, -8, 9, 10]n = len(arr)# function callprint(maxEvenLenSum(arr, n)) |
C#
using System;class GFG { static int maxEvenLenSum(int[] arr, int n) { // There has to be at least 2 elements if (n < 2) return 0; // initialize variables to store the previous values int prevPrevSum = 0, prevSum = arr[n - 2] + arr[n - 1], currSum; // iterate over subproblems and get the current // value from previous computations for (int i = n - 3; i >= 0; i--) { currSum = arr[i] + arr[i + 1]; if (prevPrevSum > 0) currSum += prevPrevSum; // assigning values for further iterations prevPrevSum = prevSum; prevSum = currSum; } // return answer return Math.Max(prevSum, prevPrevSum); } // Driver code static void Main() { int[] arr = { 8, 9, -8, 9, 10 }; int n = arr.Length; // function call Console.Write(maxEvenLenSum(arr, n)); }} |
Javascript
<script> // Javascript code for above approach function maxEvenLenSum(arr, n) { // There has to be at // least 2 elements if (n < 2) { return 0; } // Initialize variables to store the previous values let prevPrevSum = 0; let prevSum = arr[n - 2] + arr[n - 1]; let currSum; // Iterate over subproblems and get the current value from previous computations for (let i = n - 3; i >= 0; i--) { currSum = arr[i] + arr[i + 1]; if (prevPrevSum > 0) { currSum += prevPrevSum; } // Assign values for further iterations prevPrevSum = prevSum; prevSum = currSum; } // Return answer return Math.max(prevSum, prevPrevSum); } // Driver code const arr = [8, 9, -8, 9, 10]; const n = arr.length; // Function call document.write(maxEvenLenSum(arr, n)); // This code is contributed by Vaibhav Nandan</script> |
Output
20
Time complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
