One scan O(1) space DP solution
Learned from here https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/discuss/377507/c%2B%2B-dp-with-constant-space, adapted a bit.\n\ndp1 is t
Learned from here https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/discuss/377507/c%2B%2B-dp-with-constant-space, adapted a bit.\n\ndp1 is the classical max subarray sum that ends at index i, which is similar to Kadane\'s algorithm.\ndp0 means the max subarray sum that ends at index i and must have one hole. When i == 0, dp0 is undefined. When i > 0, a legit subarray with one hole can only be: s1 s2 s3 (deleted-s4) s5 ... s_i OR s1 s2 s3 s4 ... s_(i-1) (deleted s_i). Note s1 cannot be deleted.\n\nWith the above two definitions, the dp formula is intuitive.\n\n```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        optional<int> dp0;\n        int dp1 = arr[0], ans = arr[0];\n        for (int i = 1; i < arr.size(); ++i) {\n            dp0 = dp0 ? max(dp1, *dp0 + arr[i]) : dp1;\n            dp1 = max(arr[i], dp1 + arr[i]);\n            ans = max(ans, max(*dp0, dp1));\n        }\n        return ans;\n    }\n};\n```
[]