Mảng con tổng tối đa sử dụng Chia và Chinh phục trong C ++

Giả sử chúng ta có một danh sách dữ liệu với các giá trị âm và dương. Chúng ta phải tìm tổng của mảng con liền kề có tổng lớn nhất. Giả sử danh sách chứa {-2, -5, 6, -2, -3, 1, 5, -6}, thì tổng của mảng con tối đa là 7. Nó là tổng của {6, -2, -3 , 1, 5}

Chúng ta sẽ giải quyết vấn đề này bằng phương pháp Chia và Chinh phục. Các bước sẽ giống như bên dưới -

Các bước -

• Chia mảng thành hai phần
• Tìm tối đa ba thứ sau
  • Tổng mảng con tối đa của mảng con bên trái
  • Tổng mảng con tối đa của mảng con bên phải
  • Tổng mảng con tối đa sao cho mảng con vượt qua điểm giữa

Ví dụ

#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);
}

Đầu ra

Valid String