Problem 74: Maximum Subsequence Sum with One Deletion
Problem Statement: Given an array of integers, find the maximum sum of a non-empty subsequence such that at most one element may be deleted from the subsequence.
Input
The first line contains an integer n. The second line contains n space-separated integers.
Output
Print the maximum subsequence sum achievable with at most one deletion.
Examples
Input:
5
-2 -3 4 -1 -2
Output:
6
Solution Explanation
Use dynamic programming maintaining two arrays: one for maximum sum without deletion and one with deletion allowed. Transition by comparing deleting the current element or taking it.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
int n;
cin >> n;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
vector dp_no(n), dp_del(n);
dp_no[0] = a[0];
dp_del[0] = a[0];
int ans = a[0];
for(int i = 1; i < n; i++){
dp_no[i] = max(a[i], dp_no[i - 1] + a[i]);
dp_del[i] = max(dp_no[i - 1], dp_del[i - 1] + a[i]);
ans = max({ans, dp_no[i], dp_del[i]});
}
cout << ans << "\n";
return 0;
}