C++에서 최대 두 개의 요소를 반전한 후의 최대 하위 배열 합계

이 문제에서는 배열이 제공됩니다. 우리의 임무는 C++에서 최대 두 개의 요소를 반전시킨 후 최대 부분배열 합을 찾는 프로그램을 만드는 것입니다.

문제 설명 − 여기에서 배열의 두 숫자의 부호를 반전할 때 최대 합을 생성하는 하위 배열을 찾아야 합니다.

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

입력 - 배열 ={-5, 1, 3, 8, -2, 4, 7}

출력 − 30

설명 − 인덱스 0에서 6까지의 요소를 고려하고 값 -5와 -2를 반전하여 최대 합을 갖는 배열을 얻습니다.

이 문제를 해결하기 위해 동적 프로그래밍 방식을 사용합니다. 크기가 1에서 n(배열의 길이)까지의 모든 하위 배열의 최대 합을 확인합니다. 따라서 각 하위 배열에 대해 세 가지 경우가 있습니다.

사례 1 − 하위 배열의 두 요소를 반전한 후 하위 배열의 최대 합입니다.

사례2 − 하위 배열의 한 요소를 반전시킨 후 하위 배열의 최대 합입니다.

사례3 − 부분배열의 요소를 0으로 반전시킨 후의 부분배열의 최대 합입니다.

따라서 모든 반복에 대해 배열의 최대값과 현재 요소를 찾아 최대값으로 초기화합니다.

최대 합계를 maxSum이라는 2D 배열에 저장합니다. 그리고 최종 maxSum은 2D 배열의 모든 요소의 최대값입니다.

예시

솔루션 구현을 보여주는 프로그램,

#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
   int maxSubarraySum = 0;
   int* arr = new int[n + 1];
   for (int i = 1; i <= n; i++)
      arr[i] = a[i - 1];
   int** maxSum = new int*[n + 1];
   for (int i = 0; i <= n; i++)
      maxSum[i] = new int[3];
   for (int i = 1; i <= n; ++i) {
      maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
      maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
      if (i >= 2)
      maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
      if (i >= 2)
         maxSum[i][2] = maxSum[i - 1][1] - arr[i];
      if (i >= 3)
         maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
   }
   return maxSubarraySum;
}
int main(){
   int arr[] = {-5, 1, 3, 8, -2, 4, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n);
   return 0;
}

출력

Maximum subarray sum after inverting at most two elements is 30