php - 使和为奇数的最大子数组和

Question

给定一个整数数组，我必须找到具有最大总和的子数组，使得总和为奇数。

例如在数组“2,5,7”中答案是 7,2。到现在为止我遇到了 Kadane's algorithm及其实现在这里 http://pastebin.com/qwWzbxKw

但我如何扩展它，使总和为奇数。

编辑

数组的所有元素都是整数和正数

Answer 1

看来您并不要求它是连续的(从您的示例来看)。这要简单得多，只需取所有正元素，如果总和是奇数——你就完成了。如果是偶数——移除最低的正奇数元素，或者添加最高奇数的负元素(做哪个更好，它只取决于abs(highest_negative_odd)和lowest_positive_odd) .

伪代码:

1. sum <- 所有正元素的总和
2. 如果和是奇数 - 完成，返回相关的子数组
3. x <- 最高负奇数元素
4. y <- 最低正奇数元素
5. 如果 abs(x) < y
   • sum <- sum + x//将x加入子数组
6. 其他:
   • sum <- sum - y//从子数组中删除y
7. 返回相关子数组

编辑:

对于所有正数，它更容易 - 如果总和不是奇数 - 只需踢出最小的奇数。