fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int crossmaxsum(vector<int>&nums,int left,int mid,int right,int &start,int &end)
  4. {
  5. int maxleftsum=-100,maxrightsum=-100;
  6. int leftsum=0,rightsum=0;
  7. int leftidx=mid;
  8. int tempstart=mid;
  9. for(int i=mid;i>=left;i--)
  10. {
  11. leftsum=leftsum+nums[i];
  12. if(leftsum>maxleftsum)
  13. {
  14. maxleftsum=leftsum;
  15. tempstart=i;
  16. }
  17. }
  18. int rightidx=mid+1;
  19. int tempend=mid+1;
  20. for(int i=mid+1;i<=right;i++)
  21. {
  22. rightsum=rightsum+nums[i];
  23. if(rightsum>maxrightsum)
  24. {
  25. maxrightsum=rightsum;
  26. tempend=i;
  27. }
  28. }
  29. start=tempstart;
  30. end=tempend;
  31. return maxleftsum+maxrightsum;
  32. }
  33.  
  34. int Maxsubarraysum(vector<int>&nums,int left,int right,int &start,int &end)
  35. {
  36. if(left==right)
  37. {
  38. start=end=left;
  39. return nums[left];
  40. }
  41. int mid=(right+left)/2;
  42. int leftstart,leftend,rightstart,rightend,crossstart,crossend;
  43. int leftpart=Maxsubarraysum(nums,left,mid,leftstart,leftend);
  44. int rightpart=Maxsubarraysum(nums,mid+1,right,rightstart,rightend);
  45. int Crossingmaxsum=crossmaxsum(nums,left,mid,right,crossstart,crossend);
  46. if(leftpart>=rightpart&& leftpart>=Crossingmaxsum)
  47. {
  48. start=leftpart;
  49. end=leftend;
  50. return crossstart;
  51. }
  52. if(rightpart>=leftpart&& rightpart>=Crossingmaxsum)
  53. {
  54. start=rightpart;
  55. end=rightend;
  56. return crossend;
  57. }
  58. else
  59. {
  60. start=crossstart;
  61. end=crossend;
  62. return Crossingmaxsum;
  63. }
  64. }
  65. int main()
  66. {
  67. int n;
  68. cin>>n;
  69. vector<int>nums;
  70. for(int i=0;i<n;i++)
  71. {
  72. int x;
  73. cin>>x;
  74. nums.push_back(x);
  75. }
  76. int start=0,end=0;
  77. int maxsubarraysum=Maxsubarraysum(nums,0,n-1,start,end);
  78. cout<<maxsubarraysum<<endl;
  79. for(int i=start;i<=end;i++)
  80. {
  81. cout<<nums[i]<<" ";
  82. cout<<endl;
  83. }
  84. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5
3 0 1 4 5
stdout
copy 
13
3 
0 
1 
4 
5
https://ideone.com/zPeRSL
language:
C++ (gcc 8.3)
created:
14 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!