arrays - 计算最大偶数成本子数组

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 thatthat 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 秒。因此，我想把它改成动态规划。

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

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 .

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