Maximum Imbalance Partition

You are given a non-negative integer array \([a_1, a_2, \dots, a_n]\). Your task is to partition the array into exactly \(k\) non-empty contiguous segments. The imbalance of a partition is defined as the difference between the maximum segment sum and the minimum segment sum, i.e., \(\text{imbalance} = \max(S_1, S_2, \dots, S_k) - \min(S_1, S_2, \dots, S_k)\), where \(S_i\) is the sum of the \(i\)th segment. You need to compute the maximum imbalance achievable among all possible ways to partition the array into \(k\) segments.

Example:

Input: 4 2
       2 1 3 4
Possible partitions:

[2] and [1, 3, 4]  => Sums: 2 and 8, imbalance = 8 - 2 = 6
[2, 1] and [3, 4]  => Sums: 3 and 7, imbalance = 7 - 3 = 4
[2, 1, 3] and [4]  => Sums: 6 and 4, imbalance = 6 - 4 = 2

The maximum imbalance is 6.

inputFormat

The first line contains two integers \(n\) and \(k\) --- the number of elements in the array and the number of segments, respectively. The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer --- the maximum imbalance achievable when partitioning the array into exactly \(k\) contiguous segments.

sample

4 2
2 1 3 4

6