计算最大偶数成本子数组

Question

我是算法和竞争性编程的新手。我正在学习动态规划，但遇到如下问题：

Given an array with n numbers. Define a sub-array is a[i, j] = {a[i], a[i + 1], ..., a[j]}, in other words, elements must be contiguous.

The problem is the find the maximum weight of a sub-array such that that weight is an even number.

The input is 2 <= n <= 1000000; -100 <= a[i] <= 100

Sample test:

5

-2 1 -4 4 9

Output: 10

这道题可以暴力破解，但是n的值很大，不能用1秒的时间限制。所以，我想改成动态规划。

我有一个想法，但不知道行不行。我想我可以把这个问题分成两个子问题。对于每个 element/number，我考虑它是否是 odd/even，然后找到其对应的属性的最大和（奇数 + 奇数或偶数 + 偶数以获得偶数和）。然而，这正是我的想法，我真的需要你的帮助。

Answer 1

这是具有 O(n) 时间复杂度的 C++ 算法：

const int Inf = 1e9;
int main() {
    int n = 5;
    vector<int> inputArray = {-2, 1, -4, 4, 9};

    int minEvenPrefixSum = 0, minOddPrefixSum = Inf;
    bool isOddPrefixSumFound = false;
    int prefixSum = 0, answer = -Inf;
    for(int i = 0; i < n; ++i) {
        prefixSum += inputArray[i];
        if(abs(prefixSum) % 2 == 0) {
            answer = max(answer, prefixSum - minEvenPrefixSum);
            minEvenPrefixSum = min(minEvenPrefixSum, prefixSum);
        } else {
            if(isOddPrefixSumFound) {
                answer = max(answer, prefixSum - minOddPrefixSum);
            }
            isOddPrefixSumFound = true;
            minOddPrefixSum = min(minOddPrefixSum, prefixSum);
        }
    }

    if(answer == -Inf) {
        cout << "There is no subarray with even sum";
    } else {
        cout << answer;
    }
}

说明：正如@nico-schertler 在评论中提到的，此任务与最大和连续子数组的更基本问题非常相似。如何解决具有 O(n) 时间复杂度的基本任务，您可以阅读 here.

现在我们不仅要存储最小前缀和的一个值，还要存储两个。一个是最小偶数前缀和，另一个是最小奇数前缀和。结果，当我们处理下一个数字时，我们会查看前缀和的值变成什么。如果是偶数，我们尝试使用前缀和的最小偶数值更新答案，否则使用前缀和的最小奇数值。

计算最大偶数成本子数组

Calculate the maximal even cost subarray

arrays

algorithm

dynamic-programming