fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int CrossMaxSum(vector<int>&nums,int left,int mid,int right)
  4. {
  5. int maxleftsum=-100,maxrightsum=-100;
  6. int leftsum=0,rightsum=0;
  7. for(int i=mid;i>=left;i--)
  8. {
  9. leftsum=leftsum+nums[i];
  10. if(leftsum>maxleftsum)
  11. {
  12. maxleftsum=leftsum;
  13. }
  14. }
  15. for(int i=mid+1;i<=right;i++)
  16. {
  17. rightsum=rightsum+nums[i];
  18. if(rightsum>maxrightsum)
  19. {
  20. maxrightsum=rightsum;
  21. }
  22. }
  23. return maxleftsum+maxrightsum;
  24. }
  25. int MaxSubarraySum(vector<int>&nums,int left,int right)
  26. {
  27. if(left==right)
  28. {
  29. return nums[left];
  30. }
  31. int mid=(left+right)/2;
  32. int leftpart=MaxSubarraySum(nums,left,mid);
  33. int rightpart=MaxSubarraySum(nums,mid+1,right);
  34. int CrossingMaxSum=CrossMaxSum(nums,left,mid,right);
  35. return max(leftpart,max(rightpart,CrossingMaxSum));
  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 maxSubarraySum=MaxSubarraySum(nums,0,n-1);
  49. cout<<maxSubarraySum<<endl;
  50. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
6
4 1 8 4 0 2
stdout
copy 
19
https://ideone.com/YDnv8H
language:
C++ (gcc 8.3)
created:
1 day 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!