Maximum Subarray Sum with One Deletion LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maximumSum(vector<int> &a) {
4
    // Kadane's Algo
5
    // DP time: O(N) space: O(N)
6
    // dp[i][2]-->dp[i][0]->suf_del and dp[i][1]->suf_no_del
7

8
    // Space optimized time: O(N) space: O(1)
9
    int n = a.size();
10
    int suf_del = 0;
11
    int suf_no_del = a[0];
12
    int ans = a[0];
13
    for (int i = 1; i < n; i++) {
14
      suf_del = max(suf_del + a[i], suf_no_del); // suf_del
15
      suf_no_del = max(suf_no_del + a[i], a[i]); // suf_no_del
16
      ans = max({ans, suf_del, suf_no_del});
17
    }
18
    return ans;
19
  }
20
};