Tối đa hóa tổng mảng con lớn nhất sau khi loại bỏ tối đa một phần tử trong C++

Đề bài

Cho mảng arr[] N phần tử. Tìm mảng con liên tiếp có tổng lớn nhất (Kadane), sau đó được phép loại bỏ tối đa 1 phần tử từ mảng con đó để tổng còn lại lớn nhất.

Ví dụ: {1,2,3,-2,3} → mảng con max sum = {1,2,3,-2,3} sum=7. Loại -2 → {1,2,3,3} sum=9.

Thuật toán (Kadane biến đổi)

Duy trì hai giá trị khi duyệt: - maxEndingHere: tổng max kết thúc tại i (không xóa). - maxEndingHereDel: tổng max kết thúc tại i (đã xóa 1 phần tử). Cập nhật: maxEndingHereDel = max(maxEndingHereDel + arr[i], maxEndingHerePrev) (xóa arr[i] hoặc đã xóa trước đó). maxEndingHere = max(maxEndingHere + arr[i], arr[i]). Kết quả = max của cả hai trên mọi i.

Ví dụ minh họa (C++)

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

int getMaxSum(int* arr, int n) {
    int maxEndingHere = arr[0];
    int maxEndingHereDel = 0; // xóa arr[0] -> sum = 0
    int res = arr[0];

    for (int i = 1; i < n; ++i) {
        // Nếu đã xóa trước đó thì cộng arr[i], hoặc xóa arr[i] ngay (lấy maxEndingHere trước đó)
        maxEndingHereDel = max(maxEndingHereDel + arr[i], maxEndingHere);
        maxEndingHere = max(maxEndingHere + arr[i], arr[i]);
        res = max(res, max(maxEndingHere, maxEndingHereDel));
    }
    return res;
}

int main() {
    int arr[] = {1, 2, 3, -2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tong lon nhat sau khi xoa it nhat 1 phan tu = " << getMaxSum(arr, n) << endl;
    return 0;
}

Kết quả

Tong lon nhat sau khi xoa it nhat 1 phan tu = 9

Lưu ý: Code gốc trong input có logic hơi phức tạp và có thể sai. Phiên bản trên là thuật toán Kadane biến đổi chuẩn cho bài "Maximum subarray sum with one deletion".