/* ॐ नमो भगवते वासुदेवाय नमः ॐ भूर्भुव: स्व: तत्सवितुर्वरेण्यं भर्गो देवस्य धीमहि धियो यो न: प्रचोदयात्। */ // all hail Infront of almighty lord krishna (jai shri krishna ji) #include<bits/stdc++.h> #ifndef ONLINE_JUDGE #include "debug.h" #else #define print(...) 1; #endif #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long const long long INF =1e18; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ; template<typename T> using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>; const int N=1e3+10; const int K=1e3+10; const int mod = 998244353; int dp[N][K][2]; int n,k; vector<int>a(N); int recursion(int i, int j, int flag) { if(i>=n) { if(j==0) { return 0; } else { return -1e12; } } if(j==0) { return -1e12; } if(dp[i][j][flag]!=-1) { return dp[i][j][flag]; } int first=(flag==0?-1:1)*a[i] + recursion(i+1,j,flag); int second=-1e12; if(j>0) { second=(flag==0?-1:1)*a[i]+recursion(i+1,j-1,1-flag); } return dp[i][j][flag]=max(first,second); } void Solve() { cin>>n>>k; for(int i=0;i<n;i++) { cin>>a[i]; } memset(dp,-1,sizeof(dp)); int ans=recursion(0,k,0); cout<<ans<<"\n"; } signed main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); cout<<fixed; int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { // cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }