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.