//Why is it giving wrong answer? For example, for {1 2 3 4 5}, and k = 2, it is outputting 9, while it should output 6 as {1 2 3 4} and {5}. Please help
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define endl '\n'
#define INF (ll)1e15
#define MOD 1000000007
vector<vector<ll>> dp;
vector<ll> arr;
ll rec(int i, int k) {
if (i == -1) {
if (k == 0) {
return 0;
}
return INT_MIN;
}
if (dp[i][k] != -1) {
return dp[i][k];
}
ll ans = 0;
ll mini = INT_MAX;
if (k > 0) {
// THE SUBPART WE ARE CREATING IS [j,i]
for (int j = i-1; j >= -1; j--) {
mini = min(mini,arr[j+1]);
ans = max(ans,mini+rec(j,k-1));
}
}
return dp[i][k] = ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
arr.resize(n);
for (auto &x:arr) {
cin >> x;
}
dp.assign(n+5,vector<ll>(k+5,-1));
cout << rec(n-1,k) << endl;
return 0;
}
Auto comment: topic has been updated by _hopefullyme (previous revision, new revision, compare).