Maximum subarray sum such that sum is odd

1
votes

Given an array of integers I have to find the subarray with maximum sum such that the sum is odd.

For instance in the array "2,5,7" the answer is 7,2. Till now I have come across the Kadane's algorithm And its implementation here http://pastebin.com/qwWzbxKw

But how do I extend it such that the sum is odd.

EDIT

All elements of the array are Integers and positive

1
phpalgorithmsum

1 Answers

1
votes

It appears you are not requiring it to be contiguous (from your example). This is much simpler, just take all positive elements, and if sum is odd - you are done. If it is even - remove the lowest positive odd element, or add the highest odd negative element (do which is better, it depends only on abs(highest_negative_odd) and lowest_positive_odd).

Pseudo code:

  1. sum <- sum of all positive elements
  2. if sum is odd - done, return the relevant subarray
  3. x <- highest negative odd element
  4. y <- lowest positive odd element
  5. if abs(x) < y
    • sum <- sum + x //add x to the subarray
  6. else:
    • sum <- sum - y //remove y from the subarray
  7. return relevant subarray

EDIT:

For all positive number it's even easier - if the sum is not odd - just kick the smallest odd number out.