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;
}