fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void print(vector<int> &arr){
  5. 	int n = arr.size();
  6. 	for(int i = 0; i < n; i++)
  7. 	cout << arr[i] << " ";
  8. }
  9. int main() {
  10. 	int n; cin >> n;
  11. 	vector<int> arr(n);
  12. 	for(int i = 0; i < n; i++)
  13. 	cin >> arr[i];
  14.  
  15. 	vector<int> pref(n);
  16. 	vector<int> suff(n);
  17.  
  18. 	int temp = arr[0];
  19. 	pref[0] = arr[0];
  20. 	for(int i = 1; i < n; i++){
  21. 		temp = max(temp+arr[i], arr[i]);
  22. 		pref[i] = max(pref[i-1], temp);
  23. 	}
  24. 	temp = arr[n-1];
  25. 	suff[n-1] = arr[n-1];
  26. 	for(int i = n-2; i >= 0; i--){
  27. 		if(arr[i] < arr[i+1])
  28. 		temp = max(temp+arr[i], arr[i]);
  29. 		else
  30. 		temp = arr[i];
  31. 		suff[i] = max(suff[i+1], temp);
  32. 	}
  33. 	int res = INT_MIN;
  34. 	for(int i = 0; i < n-1; i++){
  35. 		res = max(pref[i]+suff[i+1], res);
  36. 	}
  37. 	cout << res;
  38. 	return 0;
  39. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
7
6 3 4 9 17 -1 -11
stdout
copy 
39
https://ideone.com/VgAfFS
language:
C++14 (gcc 8.3)
created:
9 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!