#include using namespace std; #define MAX 31000 long long n, k, a[MAX], dp[300][MAX], pref[MAX]; long long calc(int l, int r) { long long s2 = 0; s2 = pref[r] - pref[l - 1]; return max(fabs(a[l] - (s2 - a[l])), fabs(a[r] - (s2 - a[r]))); } void solve(long long i, long long l, long long r, long long gl, long long gr) { if(gl < 0)gl = 0; if(l > r)return ; long long mid = (l + r) / 2, opt = 0; for(int t = gl; t <= min(gr, mid - 2); t++) { if(dp[i][mid] < dp[i - 1][t] + calc(t + 1, mid)) { dp[i][mid] = dp[i - 1][t] + calc(t + 1, mid); opt = t; } } solve(i, l, mid - 1, gl, opt + 30); solve(i, mid + 1, r, opt - 30, gr); return ; } int main() { freopen("monkeys.in", "r", stdin); freopen("monkeys.out", "w", stdout); cin >> n >> k; k /= 2; for(int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } for(int i = 0; i <= k; i++) for(int j = 0; j <= n + 2; j++)dp[i][j] = -LLONG_MAX / 12; dp[0][0] = 0; for(int i = 1; i <= k; i++) { solve(i, 1, n, 0, n - 2); /*for(int j = 1; j <= n; j++) { for(int t = j - 2; t >= 0; t--) { dp[i][j] = max(dp[i][j], dp[i - 1][t] + calc(t + 1, j)); } }*/ } cout << dp[k][n] << endl; return 0; } /* 268 84 4781 5102 8555 8049 9069 1214 3962 1294 4170 5238 612 4130 5925 1770 6640 5536 9604 3136 4928 5329 7120 1766 9619 3785 3201 7427 9380 291 771 4885 2399 5027 5030 7232 4824 7689 4672 4141 9377 478 4495 9690 5696 9122 10019 4896 4012 5108 5114 3013 159 9748 4607 7818 5120 8871 5426 4880 9662 1158 4140 7931 4145 9401 3741 1073 1842 4257 665 7744 651 1426 7500 4834 7080 3048 955 5924 2456 1898 6665 7928 5956 9739 6238 3845 6636 7915 66 9150 5675 30 5245 517 9637 8854 8673 4646 2644 9966 1347 4375 10014 4019 387 7241 4691 7955 4422 2658 3806 1125 8373 4558 4393 9552 4555 2154 7091 7859 2582 9877 7724 1015 806 5357 432 7134 6554 8610 6026 2153 599 3839 7773 9289 4416 3399 2577 7675 8801 1601 4625 6497 7949 8706 3547 5066 3345 856 10000 9488 5238 3092 6003 934 309 5404 8793 9228 9257 3426 10053 8257 7653 7197 4326 5729 2385 7410 9786 4716 9441 9751 9110 9792 8545 5198 2253 4166 8668 3250 4924 9625 8983 2945 2499 4181 3233 10017 3233 8689 7290 10034 4020 8909 1044 8834 5831 1443 1156 3328 3914 10030 3733 8475 2847 606 4044 2384 3033 8396 75 3351 739 949 7500 575 1854 3352 17 3858 9279 2180 5465 683 902 1454 5719 847 5686 8633 7742 3413 7793 4556 992 2322 94 3204 5408 8366 1418 988 4640 1932 2903 4932 3359 9336 6233 7808 8518 6457 2829 1267 7849 2491 7226 1474 9725 3349 2975 267 3324 6546 8185 8029 ------- 92362 */