Calculate the maximal even cost subarray

user_12552748 0
Viewed 379

I am new to Algorithms and Competitive Programming. I am learning about Dynamic programming and I have a problem as below:

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

For this problem, I can do brute force but with a large value of n, I can not do it with the time limit is 1 second. Therefore, I want to change it to Dynamic programming.

I have an idea but I do not know if it works. I think I can divide this problem into two sub-problems. For each element/number, I consider if it is odd/even and then find the largest sum with its corresponding property (odd + odd or even + even to get a even sum). However, that is just what I think and I really need your help.

dynamic-programming arrays algorithm
1 Answers

Here is C++ algorithm with O(n) time complexity:

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;
    }
}

Explanation: As @nico-schertler mentioned in commentary this task is very similar with more basic problem of the maximum-sum contiguous sub array. How to solve basic task with O(n) time complexity you can read here.

Now let's store not just one value of the minimum prefix sum, but two. One is for minimum even prefix sum, and the other is for minimum odd prefix sum. As a result, when we process the next number, we look at what the value of the prefix sum becomes. If it is even, we try to update the answer using the minimum even value of the prefix sum, in the other case using the minimum odd value of the prefix sum.

user_147066010
Related