fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int CrossingMaxSum(vector <int>& nums, int left, int mid, int right)
  6. {
  7.     int maxLeftSum = -1000000000, maxRightSum = -1000000000;
  8.     int leftSum = 0, rightSum = 0;
  9.     for(int i=mid;i>=left;i--)
  10.     {
  11.         leftSum = leftSum + nums[i];
  12.         if(leftSum > maxLeftSum)
  13.             maxLeftSum = leftSum;
  14.     }
  15.     for(int i=mid+1;i<=right;i++)
  16.     {
  17.         rightSum = rightSum + nums[i];
  18.         if(rightSum > maxRightSum)
  19.             maxRightSum = rightSum;
  20.     }
  21.     return maxLeftSum + maxRightSum;
  22. }
  23.  
  24. int MaxSubSum(vector <int>& nums, int left, int right)
  25. {
  26.     if(left == right)
  27.     {
  28.         return nums[left];
  29.     }
  30.     int mid = (left+right)/2;
  31.     int leftPart = MaxSubSum(nums,left,mid);
  32.     int rightPart = MaxSubSum(nums,mid+1,right);
  33.     int crossingMaxSum = CrossingMaxSum(nums,left,mid,right);
  34.     return max(leftPart, max(rightPart, crossingMaxSum));
  35. }
  36.  
  37. int main()
  38. {
  39.     int n;
  40.     cin>>n;
  41.     vector <int> nums;
  42.     for(int i=0;i<n;i++)
  43.     {
  44.         int x;
  45.         cin>>x;
  46.         nums.push_back(x);
  47.     }
  48.     int maxSubSum = MaxSubSum(nums,0,n-1);
  49.     cout<<maxSubSum<<endl;
  50. }
  51.  
  52. //13
  53. //-3 2 1 2 -6 3 5 -2 7 -3 2 -1 2
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
13
-3 2 1 2 -6 3 5 -2 7 -3 2 -1 2
stdout
copy 
13
https://ideone.com/sgsEDH
language:
C++ (gcc 8.3)
created:
3 days 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!