//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;↵
}↵
~~~~~↵
↵
↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
