ผลรวมซับอาร์เรย์สูงสุดที่ลบได้หนึ่งองค์ประกอบใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม ต้องหาผลรวมสูงสุดของซับอาร์เรย์ (องค์ประกอบติดกัน) ที่ไม่ว่างเปล่า โดยสามารถลบองค์ประกอบได้สูงสุดหนึ่งตัว กล่าวคือ เลือกซับอาร์เรย์แล้วเลือกได้ว่าจะลบหนึ่งองค์ประกอบหรือไม่ เพื่อให้ผลรวมของที่เหลือสูงสุด โดยซับอาร์เรย์ต้องไม่ว่างหลังลบ

ตัวอย่าง: [1,-2,0,3] ผลลัพธ์: 4 (ลบ -2 แล้วได้ 1+0+3=4)

ขั้นตอนการแก้ปัญหา (Kadane แบบปรับเปลี่ยน)

• n := ขนาดของอาร์เรย์, ans := a[0]
• suff_with_del := 0, suff_without_del := a[0]
• วนลูป i จาก 1 ถึง n-1:
  • suff_with_del := max(suff_with_del + a[i], suff_without_del)
  • suff_without_del := max(a[i], suff_without_del + a[i])
  • ans := max(ans, suff_without_del, suff_with_del)
• คืนค่า ans

ตัวอย่างโค้ด (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);
}

อินพุต

[1,-2,0,3]

เอาต์พุต

4