Tổng mảng con tối đa với một lần xóa trong C++

Cho mảng số nguyên, tìm tổng lớn nhất của mảng con không rỗng (liền kề) với tối đa 1 lần xóa phần tử. Mảng con phải còn ít nhất 1 phần tử sau khi xóa.

Ví dụ: [1,-2,0,3] → Kết quả: 4 (xóa -2).

Giải thuật (DP trạng thái)

1. ans = a[0], suff_with_del = 0, suff_without_del = a[0].
2. Duyệt i = 1..n-1:
3. suff_with_del = max(suff_with_del + a[i], suff_without_del) (xóa a[i] hoặc đã xóa trước).
4. suff_without_del = max(a[i], suff_without_del + a[i]) (Kadane chuẩn).
5. ans = max(ans, suff_with_del, suff_without_del).
6. Trả về ans.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maximumSum(vector<int>& a) {
        int n = a.size();
        int ans = a[0];
        int suffix_with_deletion = 0;
        int suffix_without_deletion = a[0];
        for(int i = 1; i < n; i++) {
            suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_without_deletion);
            suffix_without_deletion = max(a[i], suffix_without_deletion + a[i]);
            ans = max({ans, suffix_without_deletion, suffix_with_deletion});
        }
        return ans;
    }
};

int main() {
    vector<int> v = {1,-2,0,3};
    Solution ob;
    cout << ob.maximumSum(v);
    return 0;
}

Đầu vào

[1,-2,0,3]

Đầu ra

4