fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main() {
  6. 	// your code goes here
  7. 	int n ; cin>>n;
  8. 	vector<int>arr(n);
  9. 	for(int i = 0 ; i<n;i++){
  10. 		cin>>arr[i];
  11. 	}
  12. 	vector<int>p4(n); //min suffix sum array
  13. 	p4[n-1]=min(0,arr[n-1]);
  14. 	int sum = arr[n-1] ; 
  15. 	for(int i = n-2;i>=0; i--){
  16. 		sum+=arr[i];
  17. 		p4[i]=min({sum,p4[i+1],0});
  18. 	}
  19. 	vector<int>p2(n);
  20. 	p2[0]= min(arr[0],0);
  21. 	for(int i = 1; i<n;i++){
  22. 		p2[i]=min({p2[i-1]+arr[i],arr[i],0});
  23. 	}
  24. 	//for each index i calcualte p2 + p4 
  25. 	int p2_p4_sum = 0 ; int minsum = INT_MAX;
  26. 	for(int i = 0 ; i<n;i++){
  27. 		if(i==n-1) p2_p4_sum = p2[i];
  28. 		else{
  29. 			p2_p4_sum = p2[i]+p4[i+1];
  30. 		}
  31.  
  32. 		minsum = min(p2_p4_sum,minsum);
  33.  
  34. 	}
  35. 	// we got the minsum 
  36. 	//answer us t_sum -2*minsum 
  37. 	int t_sum = accumulate(arr.begin(),arr.end(),0);
  38. 	cout<<t_sum-2*minsum;
  39. 	return 0;
  40.  
  41. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6
-3 4 -5 2 6 -5
stdout
copy 
19
https://ideone.com/KAQGpf
language:
C++ (gcc 8.3)
created:
18 hours 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!