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 constitute all of the array when combined We are also provided with an integer K, meaning the array must be divided into K segments.
We aren't given constraints in the problem statement. What is the optimised approach for this question.
Is it DP and if it is then what will be the state
You can notice that answer in both cases is sum of absolute values of all elements of array or if $$$a[0]>0$$$ you have to substract minimum between $$$a[0] \times 2$$$ and sum of maximum positive prefix.