Leetcode 1186: Maximum Subarray Sum with One Deletion

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/description/

Notes:

This question can be viewed as a follow-up of the Leetcode : Maximum Subarray Sum. Now we can delete one element, so we naturally divide the array into two parts:  the first part is from left to current element, and the second part is from right to current element.

Please see the code below:

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int res = arr[0], len = arr.size();
        vector<int> dp1(len, 0), dp2(len, 0);//dp1[i]: the maximum sum ending with arr[i] from left to current
        dp1[0] = arr[0];
        for(int i=1; i<len; ++i) {
            dp1[i] = max(dp1[i-1] + arr[i], arr[i]);
            res = max(res, dp1[i]);
        }
        dp2[len-1] = arr[len-1];
        for(int i=len-2; i>=0; --i) {
            dp2[i] = max(dp2[i+1] + arr[i], arr[i]);
            res = max(res, dp2[i]);
        }
        for(int i=1; i<len-1; ++i) {
            int sum = dp1[i-1] + dp2[i+1];//if arr[i]<0, it can be deleted.
            if(arr[i] > 0) sum += arr[i];
            res = max(res, sum);
        }
        return res;
    }
};