Maximize Partition Value

You are given an array of n integers and an integer k. Your task is to divide the array into exactly k non-empty, contiguous subarrays (or "parts").

For each subarray, you must calculate its "value". The value of a subarray is defined as:

(sum of its elements) - (its minimum element) + (its maximum element)

The goal is to find a partitioning of the original array into k parts such that the sum of the values of all k parts is maximized.

Return this maximum possible total value.

Input Format:

The first line contains two space-separated integers, n and k.

The second line contains n space-separated integers, representing the elements of the array.

Output Format:

Your function should return a single integer representing the maximum possible total value. The runner code will handle printing.

Notes:

The problem has optimal substructure and overlapping subproblems, making it a classic fit for dynamic programming. A state dp[i][j] could represent the maximum value achievable by splitting the first j elements of the array into i parts. To calculate dp[i][j], you would iterate through all possible split points p < j and consider the value of the last part [p...j-1].

dp[i][j] = max(dp[i-1][p] + valueofsubarray(p to j-1))