C++에서 Divide and Conquer 알고리즘을 사용한 최대 부분배열 합

양수 값과 음수 값이 있는 데이터 목록이 하나 있다고 가정합니다. 합이 가장 큰 인접 부분배열의 합을 찾아야 합니다. 목록에 {-2, -5, 6, -2, -3, 1, 5, -6}이 포함되어 있다고 가정하고 최대 하위 배열의 합은 7입니다. {6, -2, -3의 합입니다. , 1, 5}

우리는 Divide and Conquer 방법을 사용하여 이 문제를 해결할 것입니다. 단계는 다음과 같습니다 -

단계 -

• 배열을 두 부분으로 나누기
• 다음 세 가지 중 최대값 찾기
  • 왼쪽 부분배열의 최대 부분배열 합계
  • 오른쪽 부분배열의 최대 부분배열 합계
  • 하위 배열이 중간점을 가로지르는 최대 하위 배열 합계

예시

#include <iostream>
using namespace std;
int max(int a, int b) {
   return (a > b)? a : b;
}
int max(int a, int b, int c) {
   return max(max(a, b), c);
}
int getMaxCrossingSum(int arr[], int l, int m, int h) {
   int sum = 0;
   int left = INT_MIN;
   for (int i = m; i >= l; i--) {
      sum = sum + arr[i];
      if (sum > left)
      left = sum;
   }
   sum = 0;
   int right = INT_MIN;
   for (int i = m+1; i <= h; i++) {
      sum = sum + arr[i];
      if (sum > right)
      right = sum;
   }
   return left + right;
}
int maxSubArraySum(int arr[], int low, int high) {
   if (low == high)
   return arr[low];
   int mid = (low + high)/2;
   return max(maxSubArraySum(arr, low, mid), maxSubArraySum(arr, mid+1, high), getMaxCrossingSum(arr, low, mid, high));
}
int main() {
   int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
   int n = sizeof(arr)/sizeof(arr[0]);
   int max_sum = maxSubArraySum(arr, 0, n-1);
   printf("Maximum contiguous sum is %d", max_sum);
}

출력

Valid String