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. }
  51.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
9 3 0 5 1
stdout
copy 
18
https://ideone.com/DX2Cbz
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!