Problem Brief

Maximum Even Sum Subsequence

FULLTIMEOA

Given a array of n positive and negative integers, find the subsequence with the maximum even sum and display that even sum.

1Example 1

Input

arr = [-2, 2, -3, 1, 3]

Output

Explanation

The longest subsequence with even sum is 2, 1 and 3.

2Example 2

Input

arr = [-2, 2, -3, 4, 5]

Output

Explanation

The longest subsequence with even sum is 2, -3, 4 and 5.

Draft autosaves locally

public int maximumEvenSumSubsequence(int[] arr) {
  // write your code here
  // The approach to the problem can be shorted down to points:
  // 1. Sum up all positive numbers 
  // 2. If the sum is even then that will be the max sum possible 
  // 3. 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.
}

Input

arr

[-2, 2, -3, 1, 3]

Output