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 exactly into K segments.

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

Could anyone share the solution with DP state[N][K]