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