Maximum difference between sum of even and odd indexed elements of a Subarray
Given an array nums[] of size N, the task is to find the maximum difference between the sum of even and odd indexed elements of a subarray.
Examples:
Input: nums[] = {1, 2, 3, 4, -5}
Output: 9
Explanation: If we select the subarray {4, -5} the sum of even indexed elements is 4 and odd indexed elements is -5. So the difference is 9.Input: nums[] = {1}
Output: 1
Approach: The problem can be solved based on the following idea:
Find all the subarrays and the difference between the sum of even and odd indexed elements.
Follow the steps mentioned below to implement the idea:
- Find out all possible subarrays of the array nums and store them in a vector.
- Calculate the maximum difference between the sum of even and odd indexed elements for that subarray.
- Store the maximum difference between the sum of even and odd indexed elements for all the subarrays and return it.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the difference between // the sum of odd and even indexed elements int helper(vector< int > temp) { int oddSum = 0, evenSum = 0; for ( int i = 0; i < temp.size(); i++) { if (i % 2 == 0) evenSum += temp[i]; else oddSum += temp[i]; } return abs (evenSum - oddSum); } // Function to find the maximum possible difference int maximumDiff(vector< int > nums) { vector< int > temp; int val; for ( int i = 0; i < nums.size(); i++) { for ( int j = i; j < nums.size(); j++) { for ( int k = i; k <= j; k++) { temp.push_back(nums[k]); } val = max(val, helper(temp)); temp.clear(); } } return val; } // Driver Code int main() { vector< int > nums = { 1, 2, 3, 4, -5 }; // Function call int ans = maximumDiff(nums); cout << ans; return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to find the difference between // the sum of odd and even indexed elements static int helper(List<Integer> temp) { int oddSum = 0 , evenSum = 0 ; for ( int i = 0 ; i < temp.size(); i++) { if (i % 2 == 0 ) evenSum += temp.get(i); else oddSum += temp.get(i); } return Math.abs(evenSum - oddSum); } // Function to find the maximum possible difference static int maximumDiff( int [] nums) { List<Integer> temp = new ArrayList<>(); int val = Integer.MIN_VALUE; for ( int i = 0 ; i < nums.length; i++) { for ( int j = i; j < nums.length; j++) { for ( int k = i; k <= j; k++) { temp.add(nums[k]); } val = Math.max(val, helper(temp)); temp.clear(); } } return val; } public static void main(String[] args) { int [] nums = { 1 , 2 , 3 , 4 , - 5 }; // Function call int ans = maximumDiff(nums); System.out.print(ans); } } // This code is contributed by lokeshmvs21. |
Python3
# python code to implement the approach # Function to find the difference between # the sum of odd and even indexed elements def helper(temp): oddSum = 0 evenSum = 0 for i in range ( 0 , len (temp)): if (i % 2 = = 0 ): evenSum + = temp[i] else : oddSum + = temp[i] return abs (evenSum - oddSum) # Function to find the maximum possible difference def maximumDiff(nums): temp = [] val = 0 for i in range ( 0 , len (nums)): for j in range (i, len (nums)): for k in range (i, j + 1 ): temp.append(nums[k]) val = max (val, helper(temp)) temp.clear() return val # Driver Code nums = [ 1 , 2 , 3 , 4 , - 5 ] # Function call ans = maximumDiff(nums) print (ans) # This code is contributed by ksam24000 |
C#
// C# code to implement the approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to find the difference between // the sum of odd and even indexed elements static int helper(ArrayList temp) { int oddSum = 0, evenSum = 0; for ( int i = 0; i < temp.Count; i++) { if (i % 2 == 0) evenSum += ( int )temp[i]; else oddSum += ( int )temp[i]; } return Math.Abs(evenSum - oddSum); } // Function to find the maximum possible difference static int maximumDiff( int [] nums) { ArrayList temp = new ArrayList(); int val = Int32.MinValue; for ( int i = 0; i < nums.Length; i++) { for ( int j = i; j < nums.Length; j++) { for ( int k = i; k <= j; k++) { temp.Add(nums[k]); } val = Math.Max(val, helper(temp)); temp.Clear(); } } return val; } public static void Main() { int [] nums = { 1, 2, 3, 4, -5 }; // Function call int ans = maximumDiff(nums); Console.Write(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code for the above approach // Function to find the difference between // the sum of odd and even indexed elements function helper(temp) { let oddSum = 0, evenSum = 0; for (let i = 0; i < temp.length; i++) { if (i % 2 == 0) evenSum += temp[i]; else oddSum += temp[i]; } return Math.abs(evenSum - oddSum); } // Function to find the maximum possible difference function maximumDiff(nums) { let temp = []; let val = Number.MIN_VALUE; for (let i = 0; i < nums.length; i++) { for (let j = i; j < nums.length; j++) { for (let k = i; k <= j; k++) { temp.push(nums[k]); } val = Math.max(val, helper(temp)); temp = []; } } return val; } // Driver Code let nums = [1, 2, 3, 4, -5]; // Function call let ans = maximumDiff(nums); console.log(ans); // This code is contributed by Potta Lokesh |
9
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach using Prefix Sum:
The problem can be solved efficiently by using the prefix sum. Create two prefix sum arrays to store the sum of odd indexed elements and even indexed elements from the beginning to a certain index. Use them to get the sum of odd indexed and even indexed elements for each subarray.
Follow the steps mentioned below to implement the idea:
- Create two arrays (say odd[] and even[]).
- Iterate over the array from i = 0 to N-1:
- If i is odd put that element in odd[i]. Otherwise, put that in even[i].
- Add odd[i-1] to odd[i] and even[i-1] to even[i].
- Traverse over all the subarrays and get the sum of elements for that subarray.
- Find the difference and update the maximum accordingly.
- Return the maximum possible difference.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to get the sum of elements from i to j int pre(vector< int >& arr, int i, int j) { if (i == 0) return arr[j]; return arr[j] - arr[i - 1]; } // Function to get the maximum possible difference // between odd and even indexed elements of a subarray int maximumDiff(vector< int >& nums) { int n = nums.size(), val = 0, sum1, sum2; vector< int > odd(n, 0), even(n, 0); even[0] = nums[0]; // Loop to create the odd[] and even[] array for ( int i = 1; i < n; i++) { if (i % 2 == 0) even[i] = nums[i]; else odd[i] = nums[i]; odd[i] += odd[i - 1]; even[i] += even[i - 1]; } // Loop to calculate the maximum possible // difference among all subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { sum1 = pre(odd, i, j); sum2 = pre(even, i, j); val = max(val, abs (sum1 - sum2)); } } // Return the maximum possible difference return val; } // Driver code int main() { vector< int > nums = { 1, 2, 3, 4, -5 }; // Function call int ans = maximumDiff(nums); cout << ans; return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to get the sum of elements from i to j static int pre( int [] arr, int i, int j) { if (i == 0 ) return arr[j]; return arr[j] - arr[i - 1 ]; } // Function to get the maximum possible difference // between odd and even indexed elements of a subarray static int maximumDiff( int [] nums) { int n = nums.length, val = 0 , sum1, sum2; int [] odd = new int [n]; int [] even = new int [n]; even[ 0 ] = nums[ 0 ]; // Loop to create the odd[] and even[] array for ( int i = 1 ; i < n; i++) { if (i % 2 == 0 ) even[i] = nums[i]; else odd[i] = nums[i]; odd[i] += odd[i - 1 ]; even[i] += even[i - 1 ]; } // Loop to calculate the maximum possible // difference among all subarrays for ( int i = 0 ; i < n; i++) { for ( int j = i; j < n; j++) { sum1 = pre(odd, i, j); sum2 = pre(even, i, j); val = Math.max(val, Math.abs(sum1 - sum2)); } } // Return the maximum possible difference return val; } // Driver code public static void main(String[] args) { int [] nums = { 1 , 2 , 3 , 4 , - 5 }; // Function call int ans = maximumDiff(nums); System.out.print(ans); } } // This code is contributed by Pushpesh Raj. |
Python3
# Python code to implement the approach # Function to get the sum of elements from i to j def pre(arr, i, j): if (i = = 0 ): return arr[j] return arr[j] - arr[i - 1 ] # Function to get the maximum possible difference # between odd and even indexed elements of a subarray def maximumDiff(nums): n = len (nums) val = 0 odd = [ 0 ] * n even = [ 0 ] * n even[ 0 ] = nums[ 0 ] # Loop to create the odd[] and even[] array for i in range ( 1 , n): if (i % 2 = = 0 ): even[i] = nums[i] else : odd[i] = nums[i] odd[i] + = odd[i - 1 ] even[i] + = even[i - 1 ] # Loop to calculate the maximum possible # difference among all subarrays for i in range (n): for j in range (i, n): sum1 = pre(odd, i, j) sum2 = pre(even, i, j) val = max (val, abs (sum1 - sum2)) # Return the maximum possible difference return val nums = [ 1 , 2 , 3 , 4 , - 5 ] # Function call ans = maximumDiff(nums) print (ans) # This code is contributed by lokesh. |
C#
// C# code to implement the approach using System; public class GFG { // Function to get the sum of elements from i to j static int pre( int [] arr, int i, int j) { if (i == 0) return arr[j]; return arr[j] - arr[i - 1]; } // Function to get the maximum possible difference // between odd and even indexed elements of a subarray static int maximumDiff( int [] nums) { int n = nums.Length, val = 0, sum1, sum2; int [] odd = new int [n]; int [] even = new int [n]; even[0] = nums[0]; // Loop to create the odd[] and even[] array for ( int i = 1; i < n; i++) { if (i % 2 == 0) even[i] = nums[i]; else odd[i] = nums[i]; odd[i] += odd[i - 1]; even[i] += even[i - 1]; } // Loop to calculate the maximum possible // difference among all subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { sum1 = pre(odd, i, j); sum2 = pre(even, i, j); val = Math.Max(val, Math.Abs(sum1 - sum2)); } } // Return the maximum possible difference return val; } // Driver code public static void Main( string [] args) { int [] nums = { 1, 2, 3, 4, -5 }; // Function call int ans = maximumDiff(nums); Console.WriteLine(ans); } } // This code is contributed by AnkThon |
Javascript
// javascript code to implement the approach // Function to get the sum of elements from i to j function pre( arr, i, j) { if (i == 0) return arr[j]; return arr[j] - arr[i - 1]; } // Function to get the maximum possible difference // between odd and even indexed elements of a subarray function maximumDiff(nums) { let n = nums.length, val = 0, sum1, sum2; let odd=[]; let even =[]; for (let i=0;i<n;i++) { even.push(0); odd.push(0); } even[0] = nums[0]; // Loop to create the odd[] and even[] array for (let i = 1; i < n; i++) { if (i % 2 == 0) even[i] = nums[i]; else odd[i] = nums[i]; odd[i] += odd[i - 1]; even[i] += even[i - 1]; } // Loop to calculate the maximum possible // difference among all subarrays for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { sum1 = pre(odd, i, j); sum2 = pre(even, i, j); val = Math.max(val, Math.abs(sum1 - sum2)); } } // Return the maximum possible difference return val; } let nums = [ 1, 2, 3, 4, -5 ]; // Function call let ans = maximumDiff(nums); console.log(ans); // This code is contributed by garg28harsh. |
9
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us