Maximum even sum subsequence
Given a array of n positive and negative integers, find the subsequence with the maximum even sum and display that even sum.
Examples:
Input: arr[] = {-2, 2, -3, 1, 3} Output: 6 Explanation: The longest subsequence with even sum is 2, 1 and 3. Input: arr[] = {-2, 2, -3, 4, 5} Output: 8 Explanation: The longest subsequence with even sum is 2,-3,4 and 5
The approach to the problem can be shorted down to points:
- Sum up all positive numbers
- If the sum is even then that will be the max sum possible
- If the sum is not even then either subtract a positive odd number from it, or add a negative odd.
- Find maximum max odd of negative odd numbers, hence sum+a[I] (as a[I] is itself negative)
- Find minimum min odd of positive odd numbers, hence sun-a[I].
- The maximum of the both the results will be the answer.
Below is the implementation of the above approach
C++
// CPP program to find longest even sum // subsequence. #include <bits/stdc++.h> using namespace std; // Returns sum of maximum even sum subsequence int maxEvenSum( int arr[], int n) { // Find sum of positive numbers int pos_sum = 0; for ( int i = 0; i < n; ++i) if (arr[i] > 0) pos_sum += arr[i]; // If sum is even, it is our // answer if (pos_sum % 2 == 0) return pos_sum; // Traverse the array to find the // maximum sum by adding a positive // odd or subtracting a negative odd int ans = INT_MIN; for ( int i = 0; i < n; ++i) { if (arr[i] % 2 != 0) { if (arr[i] > 0) ans = max(ans, pos_sum - arr[i]); else ans = max(ans, pos_sum + arr[i]); } } return ans; } // driver program int main() { int a[] = { -2, 2, -3, 1 }; int n = sizeof (a) / sizeof (a[0]); cout << maxEvenSum(a, n); return 0; } |
Java
// Java program to find longest // even sum subsequence. class MaxevenSum { // Returns sum of maximum even sum // subsequence static int maxEvenSum( int arr[], int n) { // Find sum of positive numbers int pos_sum = 0 ; for ( int i = 0 ; i < n; ++i) if (arr[i] > 0 ) pos_sum += arr[i]; // If sum is even, it is our // answer if (pos_sum % 2 == 0 ) return pos_sum; // Traverse the array to find the // maximum sum by adding a // positive odd or subtracting a // negative odd int ans = Integer.MIN_VALUE; for ( int i = 0 ; i < n; ++i) { if (arr[i] % 2 != 0 ) { if (arr[i] > 0 ) ans = ans>(pos_sum - arr[i]) ? ans:(pos_sum - arr[i]); else ans = ans>(pos_sum + arr[i]) ? ans:(pos_sum + arr[i]); } } return ans; } // driver program public static void main(String s[]) { int a[] = {- 2 , 2 , - 3 , 1 }; System.out.println(maxEvenSum(a, a.length)); } } // This code is contributed by Prerna Saini |
Python3
# Python 3 program to find longest # even sum subsequence. INT_MIN = - 100000000 # Returns sum of maximum even # sum subsequence def maxEvenSum(arr, n): # Find sum of positive numbers pos_sum = 0 for i in range (n): if (arr[i] > 0 ): pos_sum + = arr[i] # If sum is even, it is our answer if (pos_sum % 2 = = 0 ): return pos_sum # Traverse the array to find the # maximum sum by adding a positive # odd or subtracting a negative odd ans = INT_MIN; for i in range (n): if (arr[i] % 2 ! = 0 ): if (arr[i] > 0 ): ans = max (ans, pos_sum - arr[i]) else : ans = max (ans, pos_sum + arr[i]) return ans # Driver Code a = [ - 2 , 2 , - 3 , 1 ] n = len (a) print (maxEvenSum(a, n)) # This code is contributed by sahilshelangia |
C#
// C# program to find longest // even sum subsequence. using System; class GFG { // Returns sum of maximum even sum // subsequence static int maxEvenSum( int []arr, int n) { // Find sum of positive numbers int pos_sum = 0; for ( int i = 0; i < n; ++i) if (arr[i] > 0) pos_sum += arr[i]; // If sum is even, it is our // answer if (pos_sum % 2 == 0) return pos_sum; // Traverse the array to find the // maximum sum by adding a // positive odd or subtracting a // negative odd int ans = int .MinValue; for ( int i = 0; i < n; ++i) { if (arr[i] % 2 != 0) { if (arr[i] > 0) ans = (ans > (pos_sum - arr[i])) ? ans : (pos_sum - arr[i]); else ans = (ans > (pos_sum + arr[i])) ? ans : (pos_sum + arr[i]); } } return ans; } // driver program public static void Main() { int []a = {-2, 2, -3, 1}; Console.WriteLine(maxEvenSum(a, a.Length)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find longest // even sum subsequence. // Returns sum of maximum even // sum subsequence function maxEvenSum( $arr , $n ) { // Find sum of positive numbers $pos_sum = 0; for ( $i = 0; $i < $n ; ++ $i ) if ( $arr [ $i ] > 0) $pos_sum += $arr [ $i ]; // If sum is even, it is our // answer if ( $pos_sum % 2 == 0) return $pos_sum ; // Traverse the array to find // the maximum sum by adding // a positive odd or // subtracting a negative odd $ans = PHP_INT_MIN; for ( $i = 0; $i < $n ; ++ $i ) { if ( $arr [ $i ] % 2 != 0) { if ( $arr [ $i ] > 0) $ans = max( $ans , $pos_sum - $arr [ $i ]); else $ans = max( $ans , $pos_sum + $arr [ $i ]); } } return $ans ; } // driver program $a = array ( -2, 2, -3, 1 ); $n = count ( $a ); echo maxEvenSum( $a , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // javascript program to find longest // even sum subsequence. // Returns sum of maximum even sum // subsequence function maxEvenSum(arr , n) { // Find sum of positive numbers var pos_sum = 0; for (i = 0; i < n; ++i) if (arr[i] > 0) pos_sum += arr[i]; // If sum is even, it is our // answer if (pos_sum % 2 == 0) return pos_sum; // Traverse the array to find the // maximum sum by adding a // positive odd or subtracting a // negative odd var ans = Number.MIN_VALUE; for (i = 0; i < n; ++i) { if (arr[i] % 2 != 0) { if (arr[i] > 0) ans = ans > (pos_sum - arr[i]) ? ans : (pos_sum - arr[i]); else ans = ans > (pos_sum + arr[i]) ? ans : (pos_sum + arr[i]); } } return ans; } // driver program var a = [ -2, 2, -3, 1 ]; document.write(maxEvenSum(a, a.length)); // This code is contributed by Rajput-Ji </script> |
Output
2
Time complexity : O(n)
Auxiliary Space : O(1)