# CF2064C: Remove the Ends↵
↵
[Problem — C — Codeforces](https://codeforces.net/contest/2064/problem/C)↵
[problem:2064C]↵
↵
↵
### Approach 1 (TLE): Memoized Search↵
↵
Direct memoized search using `unordered_map`. We need to combine `l` and `r` states into a single `long long` for storage. Unfortunately, TLEs on test case 5.↵
↵
```cpp↵
// Note: TLE↵
#include <bits/stdc++.h>↵
using namespace std;↵
static inline long long encodeState(int l, int r) {↵
return ((long long)l << 32) | (unsigned int)r;↵
}↵
↵
unordered_map<long long, long long> dpMemo;↵
↵
vector<int> a;↵
↵
long long dp(int l, int r) {↵
if (l > r)↵
return 0;↵
long long key = encodeState(l, r);↵
if (dpMemo.count(key))↵
return dpMemo[key];↵
long long best = -LLONG_MAX / 2;↵
for (int i = l; i <= r; i++) {↵
if (a[i] > 0) {↵
best = max(best, (long long)a[i] + dp(i + 1, r));↵
} else if (a[i] < 0) {↵
best = max(best, (long long)(-a[i]) + dp(l, i - 1));↵
}↵
}↵
dpMemo[key] = best;↵
return best;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
int n;↵
cin >> n;↵
a.resize(n + 1);↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
}↵
dpMemo.clear();↵
long long ans = dp(1, n);↵
cout << ans << "\n";↵
}↵
return 0;↵
}↵
```↵
↵
### Approach 2 (AC): Left-Right DP Merge↵
↵
Let's look for patterns:↵
- If array `a` is all positive, maximize by taking left to right: $ans=\sum^n_{i=0}a_i$↵
- If all negative, take right to left↵
- Or split: take [0,i] from left and [i+1,n] from right↵
↵
We can use two DP arrays: `p_dp` (prefix) and `s_dp` (suffix).↵
$p\_dp[i]$ represents maximum answer taking positives from left up to position i:↵
↵
$$↵
j=max(p\_dp[0...i-1])\\↵
p\_dp[i]=max(p\_dp[i],p\_dp[j]+a[i]), a[i]>0\\↵
a[i]=a[n-i+1],i=[1,n]\\↵
s\_dp[i]=max(s\_dp[i],s\_dp[j]-a[i]), a[i]<0\\↵
$$↵
↵
Important constraints:↵
$$↵
p\_dp[i]=NEGINF,a[i]<0\\↵
s\_dp[i]=NEGINF,a[i]>0↵
$$↵
↵
The third way combines prefix and suffix:↵
$$↵
combined\_ans=max(combined\_ans,p\_dp[i]+s\_dp[n-i])↵
$$↵
↵
Final answer is maximum of all three approaches:↵
$$↵
ans=max(p\_dp[n],s\_dp[n],combined\_ans)↵
$$↵
↵
Code:↵
↵
```cpp↵
/*↵
* Created by: Chixiyu↵
* Date: 2025-02-17↵
*/↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
const ll NEG_INF = -1000000000000000000LL; // -1e18↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> a(n + 1);↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
}↵
// prefix↵
vector<ll> prefix_dp(n + 1, NEG_INF);↵
ll prefix_ans;↵
ll prev_max = 0; // prevmax= max(a[0,i-1])↵
prefix_dp[0] = 0;↵
for (int i = 1; i <= n; i++) {↵
if (a[i] > 0) { // can prefix dp1↵
prefix_dp[i] = max(prefix_dp[i], a[i] + prev_max);↵
// update prev_max↵
prev_max = max(prev_max, prefix_dp[i]);↵
}↵
}↵
prefix_ans = prefix_dp[n];↵
// suffix↵
vector<ll> suffix_dp(n + 1, NEG_INF);↵
ll suffix_ans;↵
prev_max = 0;↵
// inverse the array↵
reverse(++a.begin(), a.end());↵
suffix_dp[0] = 0;↵
for (int i = 1; i <= n; i++) {↵
if (a[i] < 0) { // can suffix dp↵
suffix_dp[i] = max(suffix_dp[i], -a[i] + prev_max);↵
prev_max = max(prev_max, suffix_dp[i]);↵
}↵
}↵
suffix_ans = suffix_dp[n];↵
// calculate combined↵
ll combined_ans = NEG_INF;↵
for (int i = 0; i <= n; i++) {↵
ll left = prefix_dp[i];↵
ll right = 0;↵
if (i != n) {↵
right = suffix_dp[n - i];↵
}↵
combined_ans = max(combined_ans, left + right);↵
}↵
cout << max({prefix_ans, suffix_ans, combined_ans}) << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
```↵
↵
[Problem — C — Codeforces](https://codeforces.net/contest/2064/problem/C)↵
[problem:2064C]↵
↵
↵
### Approach 1 (TLE): Memoized Search↵
↵
Direct memoized search using `unordered_map`. We need to combine `l` and `r` states into a single `long long` for storage. Unfortunately, TLEs on test case 5.↵
↵
```cpp↵
// Note: TLE↵
#include <bits/stdc++.h>↵
using namespace std;↵
static inline long long encodeState(int l, int r) {↵
return ((long long)l << 32) | (unsigned int)r;↵
}↵
↵
unordered_map<long long, long long> dpMemo;↵
↵
vector<int> a;↵
↵
long long dp(int l, int r) {↵
if (l > r)↵
return 0;↵
long long key = encodeState(l, r);↵
if (dpMemo.count(key))↵
return dpMemo[key];↵
long long best = -LLONG_MAX / 2;↵
for (int i = l; i <= r; i++) {↵
if (a[i] > 0) {↵
best = max(best, (long long)a[i] + dp(i + 1, r));↵
} else if (a[i] < 0) {↵
best = max(best, (long long)(-a[i]) + dp(l, i - 1));↵
}↵
}↵
dpMemo[key] = best;↵
return best;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
int n;↵
cin >> n;↵
a.resize(n + 1);↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
}↵
dpMemo.clear();↵
long long ans = dp(1, n);↵
cout << ans << "\n";↵
}↵
return 0;↵
}↵
```↵
↵
### Approach 2 (AC): Left-Right DP Merge↵
↵
Let's look for patterns:↵
- If array `a` is all positive, maximize by taking left to right: $ans=\sum^n_{i=0}a_i$↵
- If all negative, take right to left↵
- Or split: take [0,i] from left and [i+1,n] from right↵
↵
We can use two DP arrays: `p_dp` (prefix) and `s_dp` (suffix).↵
$p\_dp[i]$ represents maximum answer taking positives from left up to position i:↵
↵
$$↵
j=max(p\_dp[0...i-1])\\↵
p\_dp[i]=max(p\_dp[i],p\_dp[j]+a[i]), a[i]>0\\↵
a[i]=a[n-i+1],i=[1,n]\\↵
s\_dp[i]=max(s\_dp[i],s\_dp[j]-a[i]), a[i]<0\\↵
$$↵
↵
Important constraints:↵
$$↵
p\_dp[i]=NEGINF,a[i]<0\\↵
s\_dp[i]=NEGINF,a[i]>0↵
$$↵
↵
The third way combines prefix and suffix:↵
$$↵
combined\_ans=max(combined\_ans,p\_dp[i]+s\_dp[n-i])↵
$$↵
↵
Final answer is maximum of all three approaches:↵
$$↵
ans=max(p\_dp[n],s\_dp[n],combined\_ans)↵
$$↵
↵
Code:↵
↵
```cpp↵
/*↵
* Created by: Chixiyu↵
* Date: 2025-02-17↵
*/↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
const ll NEG_INF = -1000000000000000000LL; // -1e18↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> a(n + 1);↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
}↵
// prefix↵
vector<ll> prefix_dp(n + 1, NEG_INF);↵
ll prefix_ans;↵
ll prev_max = 0; // prevmax= max(a[0,i-1])↵
prefix_dp[0] = 0;↵
for (int i = 1; i <= n; i++) {↵
if (a[i] > 0) { // can prefix dp1↵
prefix_dp[i] = max(prefix_dp[i], a[i] + prev_max);↵
// update prev_max↵
prev_max = max(prev_max, prefix_dp[i]);↵
}↵
}↵
prefix_ans = prefix_dp[n];↵
// suffix↵
vector<ll> suffix_dp(n + 1, NEG_INF);↵
ll suffix_ans;↵
prev_max = 0;↵
// inverse the array↵
reverse(++a.begin(), a.end());↵
suffix_dp[0] = 0;↵
for (int i = 1; i <= n; i++) {↵
if (a[i] < 0) { // can suffix dp↵
suffix_dp[i] = max(suffix_dp[i], -a[i] + prev_max);↵
prev_max = max(prev_max, suffix_dp[i]);↵
}↵
}↵
suffix_ans = suffix_dp[n];↵
// calculate combined↵
ll combined_ans = NEG_INF;↵
for (int i = 0; i <= n; i++) {↵
ll left = prefix_dp[i];↵
ll right = 0;↵
if (i != n) {↵
right = suffix_dp[n - i];↵
}↵
combined_ans = max(combined_ans, left + right);↵
}↵
cout << max({prefix_ans, suffix_ans, combined_ans}) << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
```↵
