Можна помітити, що для k=0, відповідь - це сума a_1 + \sum_i \max(0, a_i - a_{i-1}).
Якщо k=1, то нам вигідно зробити так, щоб певне a_i було рівне або a_{i-1}, або a_{i+1}. У такому випадку дві послідовні a_i будуть однаковими, що є найбільш вигідним. Можна помітити, що при k=1, задача фактично зводиться до того, що ми можемо видалити один елемент з . Глянемо на приклад, нехай a=[3, 1, 4]. Якщо ми видалимо другий елемент, то буде . Якщо ми замінимо , наприклад, на , то вийде [3, 4, 4]. Тоді виходять два послідовні елементи, які фактично можна об'єднати в один.
Це саме можна сказати для будь-якого . Задача зводиться до того, щоб видалити з масиву чисел.
Можемо використати метод динамічного програмування. Нехай dp[i][j] - відповідь, якщо ми переглянули перші елементів зліва, взяли -ий елемент, і взяли елементів сумарно. Формула виходить така:
Таке ДП можна порахувати за O(n^3).
Задачу можна звести до того, щоб кожному dp[i][j] присвоїти мінімум з
dp[k][j - 1], де a_k > a_i.
(dp[k][j - 1] - a_k) + a_i, де a_k \leq a_i.
Для швидкого підрахунку будемо зберігати дерев Фенвіка, половина з них буде відповідати за першу частину формули, а друга за другу. Звісно, тут також можна використовувати й дерева відрізків, проте потрібно сильно постаратися, щоб такий розв'язок не отримав ТЛ. Сумарна складність O(n ^ 2 \log n).