LeetCode 1186. Maximum Subarray Sum with One Deletion

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size(), deleted = 0, reserved = arr[0], ans = arr[0];
        for (int i = 1; i < n; ++i) {
            deleted = max(deleted + arr[i], reserved);
            reserved = max(reserved + arr[i], arr[i]);
            ans = max(ans, max(deleted, reserved));
        }
        return ans;
    }
};