Max sum of Subarray of length N/2 where sum is divisible by N
Given an array, arr[] of size N where N is even, the task is to find the maximum possible sum of the subarray of length N/2 where the sum is divisible by N.
Examples:
Input: arr[] = {2, 3, 4, 5, 6, 7}, N = 6
Output:18
Explanation: Here, N = 6, The maximum possible sum of a sublist of length 3 (N/2) is 18 (divisible by 6), which can be obtained by selecting the subarray [5, 6, 7].Input: arr[] = {3, 5, 6, 11, 7, 8}, N = 6
Output: 24
Explanation: The maximum possible sum of a sublist of length 3 (N/2) is 24 (divisible by 6), which can be obtained by selecting the subarray [6, 11, 7].
Approach: This can be solved with the following idea:
One way to solve this problem is to use Dynamic programming. We can create a 2D array DP with dimensions (N/2 + 1) x N, where DP[i][j] represents the maximum possible sum of an arr[] of length i (i.e., i = N/2) ending at index j.
Steps involved in the implementation of code:
- The base case is DP[0][j] = 0 for all j.
- For the recursive case, we can compute DP[i][j] by considering two options:
- If we include the jth element in the subarray, the sum will be divisible by N only if the sum of the previous i – 1 elements is congruent to the j % N. Therefore, we can compute DP[i][j] as DP[i – 1][(j – K + N) % N] + A[j], where K ranges from 0 to N – 1. The maximum of these values is the maximum possible sum of a subarray of length i that ends at index j.
- If we do not include the jth element in the subarray, then DP[i][j] = DP[i][j-1].
- The final answer is the maximum value in DP[N/2][j] for all j.
Below is the implementation of the above approach:
C++
// CPP approach #include <bits/stdc++.h> using namespace std; int max_sum_sublist(vector< int > arr) { // Takes in a list of n integers, // where n is even, and returns the // maximum possible sum of a sublist // such that the sum of the elements // in the sublist is divisible by n // and the length of the sublist is n/2. int n = arr.size(); vector<vector< int > > DP((n / 2 + 1), vector< int >(n + 1, 0)); // Initialize the base case for ( int j = 0; j < n; j++) DP[0][j] = 0; // Compute DP[i][j] for // i > 0 and j > 0 for ( int i = 1; i < n / 2 + 1; i++) { for ( int j = 0; j < n; j++) { DP[i][j] = 0; for ( int k = 0; k < n; k++) { if ((j - k + n) % n < j) DP[i][j] = max( DP[i][j], DP[i - 1][(j - k + n) % n] + arr[j]); } DP[i][j] = max(DP[i][j], DP[i][j - 1]); } } // Find the maximum value // in the last row of DP int max_sum = 0; for ( int j = 0; j < n; j++) max_sum = max(max_sum, DP[n / 2][j]); // Return the maximum possible sum return max_sum; } // Driver code int main() { vector< int > arr = { 2, 3, 4, 5, 6, 7 }; // Function call cout << max_sum_sublist(arr); return 0; } |
Java
// java approach import java.util.Arrays; import java.util.List; public class GFG { public static int maxSumSublist(List<Integer> arr) { // Takes in a list of n integers, // where n is even, and returns the // maximum possible sum of a sublist // such that the sum of the elements // in the sublist is divisible by n // and the length of the sublist is n/2. int n = arr.size(); int [][] DP = new int [n / 2 + 1 ][n + 1 ]; // Initialize the base case for ( int j = 0 ; j < n + 1 ; j++) DP[ 0 ][j] = 0 ; // Compute DP[i][j] for i > 0 and j > 0 for ( int i = 1 ; i < n / 2 + 1 ; i++) { for ( int j = 1 ; j < n + 1 ; j++) { DP[i][j] = 0 ; for ( int k = 0 ; k < n; k++) { if ((j - k + n) % n < j) DP[i][j] = Math.max( DP[i][j], DP[i - 1 ][(j - k + n) % n] + arr.get(j - 1 )); } DP[i][j] = Math.max(DP[i][j], DP[i][j - 1 ]); } } // Find the maximum value in the last row of DP int maxSum = 0 ; for ( int j = 1 ; j < n + 1 ; j++) maxSum = Math.max(maxSum, DP[n / 2 ][j]); // return maximum possible sum return maxSum; } // driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList( 2 , 3 , 4 , 5 , 6 , 7 ); // function call System.out.println(maxSumSublist(arr)); } } |
Python3
# Python Implementation of code import sys def max_sum_sublist(arr): # Takes in a list of n integers, # where n is even, and returns the # maximum possible sum of a sublist # such that the sum of the elements # in the sublist is divisible by n # and the length of the sublist is n/2. n = len (arr) DP = [[ 0 for j in range (n + 1 )] for i in range (n / / 2 + 1 )] # Initialize the base case for j in range (n): DP[ 0 ][j] = 0 # Compute DP[i][j] for # i > 0 and j > 0 for i in range ( 1 , n / / 2 + 1 ): for j in range (n): DP[i][j] = 0 for k in range (n): if (j - k + n) % n < j: DP[i][j] = max (DP[i][j], DP[i - 1 ][(j - k + n) % n] + arr[j]) DP[i][j] = max (DP[i][j], DP[i][j - 1 ]) # Find the maximum value # in the last row of DP max_sum = 0 for j in range (n): max_sum = max (max_sum, DP[n / / 2 ][j]) # Return the maximum possible sum return max_sum # Driver code if __name__ = = "__main__" : arr = [ 2 , 3 , 4 , 5 , 6 , 7 ] # Function call print (max_sum_sublist(arr)) # This code is contributed by Susobhan Akhuli |
C#
using System; using System.Collections.Generic; public class GFG { public static int MaxSumSublist(List< int > arr) { // Takes in a list of n integers, // where n is even, and returns the // maximum possible sum of a sublist // such that the sum of the elements // in the sublist is divisible by n // and the length of the sublist is n/2. int n = arr.Count; int [][] DP = new int [n / 2 + 1][]; for ( int i = 0; i <= n / 2; i++) { DP[i] = new int [n + 1]; } // Initialize the base case for ( int j = 0; j < n + 1; j++) { DP[0][j] = 0; } // Compute DP[i][j] for i > 0 and j > 0 for ( int i = 1; i <= n / 2; i++) { for ( int j = 1; j < n + 1; j++) { DP[i][j] = 0; for ( int k = 0; k < n; k++) { if ((j - k + n) % n < j) { DP[i][j] = Math.Max(DP[i][j], DP[i - 1][(j - k + n) % n] + arr[j - 1]); } } DP[i][j] = Math.Max(DP[i][j], DP[i][j - 1]); } } // Find the maximum value in the last row of DP int maxSum = 0; for ( int j = 1; j < n + 1; j++) { maxSum = Math.Max(maxSum, DP[n / 2][j]); } // Return the maximum possible sum return maxSum; } // Driver code public static void Main( string [] args) { List< int > arr = new List< int > { 2, 3, 4, 5, 6, 7 }; // Function call Console.WriteLine(MaxSumSublist(arr)); } } |
Javascript
function maxSumSublist(arr) { const n = arr.length; const DP = new Array(Math.floor(n / 2) + 1).fill( null ).map(() => new Array(n + 1).fill(0)); // Initialize the base case for (let j = 0; j < n + 1; j++) { DP[0][j] = 0; } // Compute DP[i][j] for i > 0 and j > 0 for (let i = 1; i < Math.floor(n / 2) + 1; i++) { for (let j = 1; j < n + 1; j++) { DP[i][j] = 0; for (let k = 0; k < n; k++) { if ((j - k + n) % n < j) { DP[i][j] = Math.max( DP[i][j], DP[i - 1][(j - k + n) % n] + arr[j - 1] ); } } DP[i][j] = Math.max(DP[i][j], DP[i][j - 1]); } } // Find the maximum value in the last row of DP let maxSum = 0; for (let j = 1; j < n + 1; j++) { maxSum = Math.max(maxSum, DP[Math.floor(n / 2)][j]); } // Return the maximum possible sum return maxSum; } // Driver code const arr = [2, 3, 4, 5, 6, 7]; // Function call console.log(maxSumSublist(arr)); |
18
Time Complexity: O(N2)
Auxiliary Space: O(N2)