Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //////////////////////////////////////////////////////////////
- // Author: Shakib Haris //
- // Problem: Maximum Subarray Problem //
- // Solution: Divide and Conquer // O(n lg n) //
- // Input: The Change(s) of Price(s), not the Price(s) //
- // Output: Maximum Subarray //
- //////////////////////////////////////////////////////////////
- #include <iostream>
- #include <climits>
- #define SIZE 10
- using namespace std;
- void findMaxCrossingSubarray(int A[], int lo, int mid, int hi, int &maxLeft, int &maxRight, int &crossSum) {
- int leftSum = INT_MIN;
- int Sum = 0;
- for (int i = mid; i >= lo; i--) {
- Sum += A[i];
- if (Sum > leftSum) {
- leftSum = Sum;
- maxLeft = i;
- }
- }
- int rightSum = INT_MIN;
- Sum = 0;
- for (int i = mid + 1; i <= hi; i++) {
- Sum += A[i];
- if (Sum > rightSum) {
- rightSum = Sum;
- maxRight = i;
- }
- }
- crossSum = leftSum + rightSum;
- return;
- }
- void findMaxSubarray(int A[], int lo, int hi, int &maxLo, int &maxHi, int &maxSum) {
- if (lo == hi) {
- maxLo = lo;
- maxHi = hi;
- maxSum = A[lo];
- return;
- }
- else {
- int mid = (lo + hi) / 2;
- int leftLo, leftHi, leftSum, rightLo, rightHi, rightSum, crossLo, crossHi, crossSum;
- findMaxSubarray(A, lo, mid, leftLo, leftHi, leftSum);
- findMaxSubarray(A, mid + 1, hi, rightLo, rightHi, rightSum);
- findMaxCrossingSubarray(A, lo, mid, hi, crossLo, crossHi, crossSum);
- if (leftSum >= rightSum && leftSum >= crossSum) {
- maxLo = leftLo;
- maxHi = leftHi;
- maxSum = leftSum;
- }
- else if (rightSum >= leftSum && rightSum >= crossSum) {
- maxLo = rightLo;
- maxHi = rightHi;
- maxSum = rightSum;
- }
- else {
- maxLo = crossLo;
- maxHi = crossHi;
- maxSum = crossSum;
- }
- return;
- }
- }
- void display (int A[], int lo, int hi) {
- for (int i = lo; i <= hi; i++)
- cout << A[i] << " ";
- cout << endl << endl;
- }
- int main() {
- int A[SIZE];
- for (int i = 0; i < SIZE; i++)
- cin >> A[i];
- cout << "Original Array: ";
- display(A, 0, SIZE - 1);
- int lo, hi, Sum;
- findMaxSubarray(A, 0, SIZE - 1, lo, hi, Sum);
- cout << "Max Sum: " << Sum << endl;
- cout << "Sub-array: ";
- display(A, lo, hi);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement