C++에서 배열의 최대 평형 합계

문제 설명

주어진 배열 arr[]. arr[]에서 인덱스 i에 대한 접미사 합이기도 한 접두사 합의 최대값을 찾습니다.

예시

입력 배열이 -

Arr[] ={1, 2, 3, 5, 3, 2, 1} 그러면 출력은 −

• 접두어 합계 =arr[0..3] =1 + 2 + 3 + 5 =11 및
• 접미사 합계 =arr[3..6] =5 + 3 + 2 + 1 =11

알고리즘

• 배열을 탐색하고 배열 presum[]의 각 인덱스에 대한 접두사 합계를 저장합니다. 여기서 presum[i]는 하위 배열 arr[0..i]의 합계를 저장합니다.
• 배열을 다시 탐색하고 접미사 합계를 다른 배열 suffsum[]에 저장합니다. 여기서 suffsum[i]은 하위 배열 arr[i..n-1]의 합계를 저장합니다.
• 각 인덱스에 대해 presum[i]이 suffsum[i]와 같은지 확인하고 같으면 지금까지 전체 최대값과 비교합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
   int preSum[n];
   int suffSum[n];
   int result = INT_MIN;
   preSum[0] = arr[0];
   for (int i = 1; i < n; ++i) {
      preSum[i] = preSum[i - 1] + arr[i];
   }
   suffSum[n - 1] = arr[n - 1];
   if (preSum[n - 1] == suffSum[n - 1]) {
      result = max(result, preSum[n - 1]);
   }
   for (int i = n - 2; i >= 0; --i) {
      suffSum[i] = suffSum[i + 1] + arr[i];
      if (suffSum[i] == preSum[i]) {
         result = max(result, preSum[i]);
      }
   }
   return result;
}
int main() {
   int arr[] = {1, 2, 3, 5, 3, 2, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Max equlibrium sum = 11