第一时间竟然想的是找到所有subset。。。。真的想死
看题目确定步骤:
- 因为找maximum sum，所以数组里的负数可以完全不管，甚至题目里给出了可以完全不选的选项，所以第一步直接去掉负数，看正数和
- 如果正数和是偶数，那我们找到了答案，如果不是，我们可以减去最小的正奇数或加上最大的负奇数
变形1：找到最小even/最大odd/最小odd
相同做法
变形2: 去掉可以完全不选的选项
继承之前的想法，加上一个加过正数的flag，如果加过正数，照常进行。如果没有，则取最小负偶数和两个最小负奇数之和中符合条件的一项