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

Trong bài toán này, chúng ta được cung cấp một mảng. Nhiệm vụ của chúng ta là tạo một chương trình tìm mảng con có tổng tối đa loại bỏ nhiều nhất một phần tử trong c ++.

Về cơ bản, chúng ta cần tìm một phần tử mà khi bị xóa sẽ cung cấp tổng tối đa cho các phần tử còn lại trong mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={5, 1, 9, 2, -1, 7}

Đầu ra - 24

Giải thích - chúng tôi đã xóa -1 khỏi mảng và tổng trở thành giá trị lớn nhất của tất cả các kết quả có thể có.

Một giải pháp cho vấn đề này là tìm phần tử nhỏ nhất của mảng và sau đó tìm tổng của tất cả các phần tử còn lại của mảng.

Nhưng ở đây, điều kiện loại bỏ phần tử không được áp dụng, thuật toán của kadane sẽ giải quyết vấn đề theo cách tốt hơn. Vì vậy, ở đây chúng tôi sẽ tính toán tổng tối đa theo cách mà chúng tôi sẽ tìm thấy tổng cho đến phần tử thứ i từ đầu và từ cuối.

Và sau đó kiểm tra phần tử thứ i nào khi bị bỏ qua bằng cách sử dụng mảng tổng bắt đầu và kết thúc, sau đó in tổng sau khi bỏ qua phần tử đã cho.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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<;"The maximum subarray after removing one element is "<<maxSubarraySum(array, n);
   return 0;
}

Đầu ra

The maximum subarray after removing one element is 28