FREEDUROV

The freedom of pavel durov, our father. I will now write the same from all of our accounts.

Given an array of length N with elements array[i] (negative integers inclusive), maximize the Score of the array.

Score of the array = -seg[1] + seg[2] — seg[3] + seg[4].... where all seg[i] are the sum of non-intersecting segments of the array which (case 1: constitute all of the array when combined, case 2: don't necessarily constitute all of the array when combined).

We aren't given constraints in the problem statement. What is the optimised approach for this question considering both cases.

Is it DP and if it is then what will be the state