C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で分割統治アルゴリズムを使用した最大サブアレイ合計


正の値と負の値を持つデータのリストが1つあるとします。合計が最大である連続するサブ配列の合計を見つける必要があります。リストに{-2、-5、6、-2、-3、1、5、-6}が含まれているとすると、最大サブ配列の合計は7になります。これは{6、-2、-3の合計です。 、1、5}

この問題は、分割統治法を使用して解決します。手順は次のようになります-

手順

  • アレイを2つの部分に分割します
  • 次の3つのうち最大のものを見つけます
    • 左側のサブアレイの最大サブアレイ合計
    • 右サブアレイの最大サブアレイ合計
    • サブアレイが中点を横切るようなサブアレイの最大合計

#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

  1. C++で分割統治法を使用した最大合計サブアレイ

    正の値と負の値を持つデータのリストが1つあるとします。合計が最大である連続するサブ配列の合計を見つける必要があります。リストに{-2、-5、6、-2、-3、1、5、-6}が含まれているとすると、最大サブ配列の合計は7になります。これは{6、-2、-3の合計です。 、1、5} この問題は、分割統治法を使用して解決します。手順は次のようになります- 手順 − アレイを2つの部分に分割します 次の3つの最大値を見つけます 左側のサブアレイの最大サブアレイ合計 右サブアレイの最大サブアレイ合計 サブアレイが中点を横切るようなサブアレイの最大合計 例 #include <iostr

  2. 二分探索アプローチを使用して最大サブアレイ合計を見つけるC++プログラム

    二分探索は、実行時の複雑さがΟ(log n)の高速検索アルゴリズムです。この検索アルゴリズムは、分割統治の原則に基づいて機能します。このアルゴリズムが正しく機能するためには、データ収集がソートされた形式である必要があります。 バイナリ検索は、コレクションの真ん中のアイテムを比較することによって特定のアイテムを検索します。一致する場合は、アイテムのインデックスが返されます。中央のアイテムがアイテムよりも大きい場合、そのアイテムは中央のアイテムの左側にあるサブ配列で検索されます。それ以外の場合、アイテムは中央のアイテムの右側のサブ配列で検索されます。このプロセスは、サブアレイのサイズがゼロになる