arraySplit

Cho một dãy số đã được sắp xếp theo thứ tự không giảm a1, a2, ... an (với mỗi j>i ta luôn có aj≥ai) và một số nguyên k.

Nhiệm vụ của bạn là chia dãy a thành k dãy con liên tiếp không rỗng (mỗi phần tử trong dãy a chỉ thuộc chính xác một dãy con) . Với mỗi dãy con ta có vi=max(i)-min(i) (max(i), min(i) là giá trị lớn nhất, nhỏ nhất của dãy con thứ i). Tìm giá trị nhỏ nhất của S = v1+v2+...+vk.

Ví dụ:

• Với a=[2,4,5,5,8,11,19], k=3 thì arraySplit(a, k) = 13. 
  Dãy a được chia thành 3 dãy con [2,4,5,5], [8,11], [19] . Dãy v sẽ là [3, 3, 0] . Tống S = 3+3+0 = 6.
• Với a=[1,3,3,7] , k=3 thì arraySplit(a, k) = 0.
  Dãy a được chia thành 3 dãy con [1], [3,3], [7]. Dãy v sẽ là [0, 0, 0]. tống S = 0.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS, Go
• [Đầu vào] array a, integer k
  1 ≤ k ≤ n ≤ 3•105
1 ≤ ai ≤ 109
• [Đầu ra] integer
  Kết quả là giá trị nhỏ nhất của S