C++의 최대 합계 비트 하위 배열

이 문제에서는 배열 arr[]이 제공됩니다. 우리의 임무는 C++에서 최대 합 비트론 하위 배열을 찾는 프로그램을 만드는 것입니다.

Bitonic 하위 배열 요소가 먼저 엄격하게 증가하고 특정 지점에 도달한 후 엄격하게 감소하는 특수 하위 배열입니다.

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

입력

arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1}

출력

30

설명

비트 하위 배열은 [2, 3, 7, 9, 6, 3]입니다. 합계 =2 + 3 + 7 + 9 + 6 + 3 =30

솔루션 접근 방식

해법은 bitonic 부분수열 문제의 해법과 유사합니다. 두 개의 배열 incSubArr[] 및 decSubArr[]을 생성합니다. 그러면 저장소 증가 및 감소 하위 배열이 생성됩니다. 인덱스 i에서 incSubArr[i]는 0에서 i까지 증가하는 하위 배열을 찾습니다. 그리고 decSubArr[i]는 i에서 N으로 증가하는 하위 배열을 찾습니다.

maxSum은 (incSubArr[i] + decSubArr[i] - arr[i])로 계산된 최대값입니다.

예시

솔루션의 작동을 설명하는 프로그램,

#include <iostream>
using namespace std;
int findMaxSumBiTonicSubArr(int arr[], int N){
   int incSubArr[N], decSubArr[N];
   int max_sum = -1;
   incSubArr[0] = arr[0];
   for (int i=1; i<N; i++)
      if (arr[i] > arr[i-1])
         incSubArr[i] = incSubArr[i-1] + arr[i];
      else
         incSubArr[i] = arr[i];
   decSubArr[N-1] = arr[N-1];
   for (int i= (N-2); i>=0; i--)
      if (arr[i] > arr[i+1])
         decSubArr[i] = decSubArr[i+1] + arr[i];
      else
         decSubArr[i] = arr[i];
   for (int i=0; i<N; i++)
      if(max_sum < (incSubArr[i] + decSubArr[i] - arr[i]))
max_sum = incSubArr[i] + decSubArr[i] - arr[i];
   return max_sum;
}
int main(){
   int arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The Maximum Sum of Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N);
   return 0;
}

출력

The Maximum Sum of Bitonic Subarray is 30