fork download
copy 
  1. //Maximum Sub-array Problem using Divide and Conquer approach
  2.  
  3. #include<iostream>
  4. #include<tuple>
  5. #include<vector>
  6. #define INF -10000000
  7. using namespace std;
  8.  
  9. int MaxCrossSum(vector<int>& A,int low,int mid,int high)
  10. {
  11.     int left_sum=INF;
  12.     int sum=0,max_left,max_right;
  13.     for(int i=low;i<=mid;i++)
  14.     {
  15.         sum=sum+A[i];
  16.         if(sum>left_sum)
  17.         {
  18.             left_sum=sum;
  19.             max_left=i;
  20.         }
  21.     }
  22.     int right_sum=INF;
  23.     sum=0;
  24.     for(int i=mid+1;i<=high;++i)
  25.     {
  26.         sum=sum+A[i];
  27.         if(sum>right_sum)
  28.         {
  29.             right_sum=sum;
  30.             max_right=i;
  31.         }
  32.     }
  33.     return left_sum+right_sum;
  34. }
  35.  
  36.  
  37. int MaxSubarraySum(vector<int>& A,int low,int high)
  38. {
  39.  
  40.     if(low==high)
  41.     {
  42.         return A[low];
  43.     }
  44.     else
  45.     {
  46.         int left_low,left_high,right_low,right_high,right_sum,left_sum,cross_low,cross_high,cross_sum;
  47.         int mid=(low+high)/2;
  48.         left_sum=MaxSubarraySum(A,low,mid);
  49.         right_sum=MaxSubarraySum(A,mid+1,high);
  50.         cross_sum=MaxCrossSum(A,low,mid,high);
  51.  
  52.         if(left_sum>=right_sum && left_sum>=cross_sum)
  53.         {
  54.             return left_sum;
  55.         }
  56.  
  57.         if(right_sum>=left_sum && right_sum>=cross_sum)
  58.         {
  59.             return right_sum;
  60.         }
  61.         else
  62.             return cross_sum;
  63.     }
  64. }
  65.  
  66. int main()
  67. {
  68.     vector<int> A={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22};
  69.     int tup=MaxSubarraySum(A,0,12);
  70.     cout<<tup;
  71. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
56
https://ideone.com/hThJgI
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!