How to approach problem D of #ABC125 contest on atcoder?



I know it should be solved using dynamic programming. I tried to solve it for a while. Implemented it with my idea. But it was giving wrong output for sample test case 2. Don’t know where I went wrong. Need help.

Here is the problem link: Problem

Here is my code: Code


I’m not sure, but I think it’s enough to count how many negative numbers you have. Then, while reading, keep track of the sum of the modules and the minimum number. If the number of negative numbers is odd then the maximum is the difference of the sum with the minimum number otherwise it is the maximum. As a minimum number I mean, absolute form.