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

Tuyên bố vấn đề

Cho một mảng arr [] gồm N số nguyên. Nhiệm vụ đầu tiên là tìm tổng mảng con tối đa và sau đó loại bỏ nhiều nhất một phần tử khỏi mảng con. Loại bỏ nhiều nhất một phần tử sao cho tổng tối đa sau khi loại bỏ là cực đại.

Nếu mảng đầu vào đã cho là {1, 2, 3, -2, 3} thì tổng mảng con tối đa là {2, 3, -2, 3}. Sau đó, chúng ta có thể loại bỏ -2. Sau khi loại bỏ mảng còn lại trở thành−

{1, 2, 3, 3} with sum 9 which is maximum.

Thuật toán

1. Use Kadane’s algorithm to find the maximum subarray sum.
2. Once the sum has beens find, re-apply Kadane’s algorithm to find the maximum sum again with some minor changes)

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int getMaxSubarraySum(int *arr, int n){
   int max = INT_MIN;
   int currentMax = 0;
   for (int i = 0; i < n; ++i) {
      currentMax = currentMax + arr[i];
      if (max < currentMax) {
         max = currentMax;
      }
      if (currentMax < 0) {
         currentMax = 0;
      }
   }
   return max;
}
int getMaxSum(int *arr, int n){
   int cnt = 0;
   int minVal = INT_MAX;
   int minSubarr = INT_MAX;
   int sum = getMaxSubarraySum(arr, n);
   int max = INT_MIN;
   int currentMax = 0;
   for (int i = 0; i < n; ++i) {
      currentMax = currentMax + arr[i];
      ++cnt;
      minSubarr = min(arr[i], minSubarr);
      if (sum == currentMax) {
         if (cnt == 1) {
            minVal = min(minVal, 0);
         } else {
            minVal = min(minVal, minSubarr);
         }
      }
      if (currentMax < 0) {
         currentMax = 0;
         cnt = 0;
         minSubarr = INT_MAX;
      }
   }
   return sum - minVal;
}
int main(){
   int arr[] = {1, 2, 3, -2, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau−

Maximum sum = 9