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

Trong bài toán này, ta được cho một mảng. Nhiệm vụ: viết chương trình tìm tổng dãy con lớn nhất sau khi loại bỏ tối đa một phần tử trong C++.

Về cơ bản, ta cần tìm một phần tử mà khi loại bỏ nó, tổng các phần tử còn lại là lớn nhất trong tất cả các trường hợp.

Hãy xem ví dụ:

Input – array = {5, 1, 9, 2, -1, 7}

Output – 24

Giải thích – loại bỏ -1, tổng trở thành lớn nhất.

Một cách đơn giản là tìm phần tử nhỏ nhất và tính tổng các phần tử còn lại. Nhưng điều kiện loại bỏ không được áp dụng, thuật toán Kadane sẽ giải quyết tốt hơn. Ta tính tổng lớn nhất sao cho: tìm tổng đến phần tử i từ đầu và từ cuối.

Sau đó kiểm tra phần tử i nào khi bỏ qua dùng mảng tổng từ đầu và cuối, in tổng sau khi bỏ phần tử đó.

Ví dụ

Chương trình minh họa triển khai giải pháp:

#include <bits/stdc++.h> using namespace std; int maxSubarraySum(int array[], int n){    int startSum[n], endSum[n];    int maxSum = array[0], overAllMax = array[0];    startSum[0] = array[0];    for (int i = 1; i < n; i++){       maxSum = max(array[i], maxSum + array[i]);       overAllMax = max(overAllMax, maxSum);       startSum[i] = maxSum;    }    maxSum = endSum[n-1] = array[n-1];    for (int i = n-2; i >= 0; i--){       maxSum = max(array[i], maxSum + array[i]);       overAllMax = max(overAllMax, maxSum);       endSum[i] = maxSum;    }    int SubArraySum = overAllMax;    for (int i = 1; i < n - 1; i++)    SubArraySum = max(SubArraySum, startSum[i - 1] + endSum[i + 1]);    return SubArraySum; } int main() {    int array[] = {5, 7, 1, -1, 4, 2, 9};    int n = sizeof(array) / sizeof(array[0]);    cout<<"Tổng dãy con lớn nhất sau khi loại bỏ một phần tử là "<<maxSubarraySum(array, n);    return 0; }

Kết quả

Tổng dãy con lớn nhất sau khi loại bỏ một phần tử là 28