fork download
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7. // your code goes here
  8. int n;
  9. cin>>n;
  10. vector<int> arr(n);
  11. for(int i=0;i<n;i++){
  12. cin>>arr[i];
  13. }
  14.  
  15. vector<int> suffix(n,0);
  16. vector<int> suffix_max(n,0);
  17. suffix[n-1]=arr[n-1];
  18. suffix_max[n-1]=arr[n-1];
  19.  
  20.  
  21. for(int i=n-2;i>=0;i--){
  22. suffix[i]=suffix[i+1]+arr[i];
  23. suffix_max[i]=max(suffix_max[i+1],suffix[i]);
  24. }
  25.  
  26. int prefix_sum=0;
  27. int ans=0;
  28. for(int i=0;i<n;i++){
  29. prefix_sum+=arr[i];
  30. int suffix_sum=0;
  31.  
  32. if(i+1<n){
  33. suffix_sum=suffix_max[i+1];
  34. }
  35. int best_sum=prefix_sum + suffix_sum;
  36. ans=max(ans,best_sum);
  37. }
  38.  
  39. cout<<ans<<endl;
  40.  
  41. return 0;
  42. }
Success #stdin #stdout 0s 5352KB
stdin
6
1 2 3 -4 4 5
stdout
15