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. vector<int> u(n,0);
  18.  
  19. suffix_max[n-1]=arr[n-1];
  20. suffix[n-1]=arr[n-1];
  21. u[n-1]=arr[n-1];
  22.  
  23.  
  24. for(int i=n-2;i>=0;i--){
  25. if(arr[i]<arr[i+1]){
  26. suffix[i]=suffix[i+1]+arr[i];}
  27. else{
  28. suffix[i]=arr[i];
  29. }
  30. u[i]=max(arr[i],suffix[i]);
  31. suffix_max[i]=max(suffix_max[i+1],u[i]);
  32.  
  33.  
  34. }
  35.  
  36. int prefix_sum=0;
  37. int ans=INT_MIN;
  38. for(int i=0;i<n;i++){
  39. prefix_sum+=arr[i];
  40. int suffix_sum=0;
  41.  
  42. if(i+1<n){
  43. suffix_sum=suffix_max[i+1];
  44. }
  45. int best_sum=prefix_sum + suffix_sum;
  46. ans=max(ans,best_sum);
  47. }
  48.  
  49. cout<<ans<<endl;
  50.  
  51. return 0;
  52. }
Success #stdin #stdout 0s 544KB
stdin
7
6 3 4 9 17 -1 -11
stdout
39