Advertisement
skb50bd

Maximum_Subarray_Problem [DivideAndConquer]

Sep 28th, 2016
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. //////////////////////////////////////////////////////////////
  2. //      Author: Shakib Haris                                //
  3. //      Problem: Maximum Subarray Problem                   //
  4. //      Solution: Divide and Conquer // O(n lg n)           //
  5. //      Input: The Change(s) of Price(s), not the Price(s)  //
  6. //      Output: Maximum Subarray                            //
  7. //////////////////////////////////////////////////////////////
  8.  
  9. #include <iostream>
  10. #include <climits>
  11. #define SIZE 10
  12.  
  13. using namespace std;
  14.  
  15.  
  16. void findMaxCrossingSubarray(int A[], int lo, int mid, int hi, int &maxLeft, int &maxRight, int &crossSum) {
  17.     int leftSum = INT_MIN;
  18.     int Sum = 0;
  19.     for (int i = mid; i >= lo; i--) {
  20.         Sum += A[i];
  21.         if (Sum > leftSum) {
  22.             leftSum = Sum;
  23.             maxLeft = i;
  24.         }
  25.     }
  26.  
  27.     int rightSum = INT_MIN;
  28.     Sum = 0;
  29.     for (int i = mid + 1; i <= hi; i++) {
  30.         Sum += A[i];
  31.         if (Sum > rightSum) {
  32.             rightSum = Sum;
  33.             maxRight = i;
  34.         }
  35.     }
  36.  
  37.     crossSum = leftSum + rightSum;
  38.     return;
  39. }
  40.  
  41.  
  42. void findMaxSubarray(int A[], int lo, int hi, int &maxLo, int &maxHi, int &maxSum) {
  43.     if (lo == hi) {
  44.         maxLo = lo;
  45.         maxHi = hi;
  46.         maxSum = A[lo];
  47.         return;
  48.     }
  49.     else {
  50.         int mid = (lo + hi) / 2;
  51.         int leftLo, leftHi, leftSum, rightLo, rightHi, rightSum, crossLo, crossHi, crossSum;
  52.         findMaxSubarray(A, lo, mid, leftLo, leftHi, leftSum);
  53.         findMaxSubarray(A, mid + 1, hi, rightLo, rightHi, rightSum);
  54.         findMaxCrossingSubarray(A, lo, mid, hi, crossLo, crossHi, crossSum);
  55.  
  56.         if (leftSum >= rightSum && leftSum >= crossSum) {
  57.             maxLo = leftLo;
  58.             maxHi = leftHi;
  59.             maxSum = leftSum;
  60.         }
  61.         else if (rightSum >= leftSum && rightSum >= crossSum) {
  62.             maxLo = rightLo;
  63.             maxHi = rightHi;
  64.             maxSum = rightSum;
  65.         }
  66.         else {
  67.             maxLo = crossLo;
  68.             maxHi = crossHi;
  69.             maxSum = crossSum;
  70.         }
  71.         return;
  72.     }
  73. }
  74.  
  75.  
  76. void display (int A[], int lo, int hi) {
  77.     for (int i = lo; i <= hi; i++)
  78.         cout << A[i] << " ";
  79.     cout << endl << endl;
  80. }
  81.  
  82.  
  83. int main() {
  84.     int A[SIZE];
  85.  
  86.     for (int i = 0; i < SIZE; i++)
  87.         cin >> A[i];
  88.  
  89.     cout << "Original Array: ";
  90.     display(A, 0, SIZE - 1);
  91.  
  92.     int lo, hi, Sum;
  93.  
  94.     findMaxSubarray(A, 0, SIZE - 1, lo, hi, Sum);
  95.  
  96.     cout << "Max Sum: " << Sum << endl;
  97.     cout << "Sub-array: ";
  98.     display(A, lo, hi);
  99.  
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement