C++에서 최대 하나의 요소를 제거하는 최대 합계 하위 배열

이 문제에서는 배열이 제공됩니다. 우리의 임무는 C++에서 최대 하나의 요소를 제거하는 최대 합 하위 배열을 찾는 프로그램을 만드는 것입니다.

기본적으로 제거될 때 배열에 남아 있는 요소의 최대 합계를 제공하는 하나의 요소를 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={5, 1, 9, 2, -1, 7}

출력 − 24

설명 − 배열에서 -1을 제거하고 합계가 가능한 모든 결과의 최대값이 되었습니다.

이 문제에 대한 한 가지 해결책은 배열의 최소 요소를 찾은 다음 배열의 나머지 모든 요소의 합을 찾는 것입니다.

하지만 여기에서는 요소 제거 조건이 적용되지 않습니다. kadane의 알고리즘 더 나은 방법으로 문제를 해결할 것입니다. 그래서 여기에서 우리는 시작과 끝에서 i번째 요소까지 합을 찾는 방식으로 최대 합을 계산할 것입니다.

그런 다음 시작 및 끝 합계 배열을 사용하여 건너뛸 때 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;
}

출력

The maximum subarray after removing one element is 28