ankit dave ankit dave - 2 months ago 5
Java Question

How do you find the max even sum from an array with using a number only once?

I am having a trivial problem of finding a max even sum from an array in java.
for ex:
In an array {1,2,3,4,5,6}
The max even sum should be 16(1+2+3+4+6) out of 6(1+2+3),10(1+2+3+4) and 16.

But as of now,I am getting 10 as an output,because it is taking sum as an contiguous sum.
Please help me with it.

Answer

Appreciate that you will do one of two things with the total sum of all elements in the array. If the total sum be even, you return that number, but if it be odd, then you will have to remove a number in order to make it even. Note that removing an even number will leave the remaining sum odd, so there is no point in removing an even number. But, since the total sum be odd, then there must be at least one odd number in the array.

So all you need to do if the total sum be odd is to iterate over the array and remove the smallest odd number. And there is guaranteed to be at least one odd number.

Here is an implementation:

public int findMaxEvenSum(int[] array) {
    int total = 0;

    for (int i=0; i < array.length; ++i) {
        total += array[i];
    }

    if (total % 2 == 0) {
        return total;
    }

    // otherwise iterate over the array and remove the smallest odd
    // number from the sum
    int lastOdd = 0;

    for (int i=0; i < array.length; ++i) {
        if (array[i] % 2 == 1 && (lastOdd == 0 || array[i] < lastOdd)) {
            total += lastOdd;
            total -= array[i];
            lastOdd = array[i];
        }
    }

    return total;
}