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
assume if 1st element is negative then simply answer is sum of absolute value of all elements
otherwise we give seg1 to any prefix and it it benificial to end prefix in such a place such that seg2 starts with positive elements then we can just take absolute of all values from that index so just find maximum of sum(pref[i])+sum(suff[i+1]) for all i where suff[i] contain sum of absolute values of suffix from i to n and pref[i] is sum of from 1 to i
thanks