leetcode1186 Maximum Subarray Sum with One Deletion

思路：

最大子段和的变体，前后两个方向分别扫一遍即可。

实现：

 1 class Solution
 2 {
 3 public:
 4     int maximumSum(vector<int>& arr)
 5     {
 6         int n = arr.size();
 7         if (n == 1) return arr[0];
 8         vector<int> f(n), b(n);
 9         int minn = 0, sum = 0;
10         for (int i = 0; i < n; i++)
11         {
12             sum += arr[i];
13             f[i] = sum - minn;
14             minn = min(minn, sum);
15         }
16         minn = sum = 0;
17         for (int i = n - 1; i >= 0; i--)
18         {
19             sum += arr[i];
20             b[i] = sum - minn;
21             minn = min(minn, sum);
22         }
23         int ans = *max_element(f.begin(), f.end());
24         for (int i = 0; i < n; i++)
25         {
26             if (arr[i] > 0) continue;
27             ans = max(ans, (i > 0 ? f[i - 1] : 0) + (i < n - 1 ? b[i + 1] : 0));
28         }
29         return ans;
30     }
31 }