fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #include<bits/stdc++.h>
  4.  
  5. int main() {
  6. 	// your code goes here
  7. 	int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
  8. 	int n = sizeof(arr)/sizeof(int);
  9. 	//p1 is prefix sum (maximum sub array sum ending at index i  
  10. 	vector<int>p1(n);
  11. 	p1[0]=max(arr[0],0);
  12. 	for(int i = 1 ; i< n ; i++){
  13. 		p1[i] = max({p1[i-1]+arr[i] , arr[i],0});
  14. 	}
  15. 	//now create maximum subb array sum starting at index i ( p2 suffix sum )
  16. 	vector<int>p2(n);
  17. 	p2[n-1]=max(arr[n-1],0);
  18. 	for(int i = n-2;i>=0;i--){
  19. 		p2[i]=max({p2[i+1]+arr[i],arr[i],0});
  20. 	}
  21. 	vector<int>max_p1(n); //max of max sub array sum ending at i 
  22. 	max_p1[0]=p1[0];
  23. 	for(int i = 1;i<n;i++){
  24. 		max_p1[i]=max(max_p1[i-1],p1[i]);
  25. 	}
  26. 	vector<int>max_p2(n); //max of max sub array sum starting at i 
  27. 	max_p2[n-1]=p2[n-1];
  28. 	for(int i = n-2;i>=0;i--){
  29. 		max_p2[i]=max(max_p2[i+1],p2[i]);
  30. 	}
  31. 	int max_sum = INT_MIN;
  32. 	for(int stick =0;stick<n-1;stick++){
  33. 		int left_maxsum = max_p1[stick];
  34. 		int right_maxsum=max_p2[stick+1];
  35. 		max_sum = max(left_maxsum+right_maxsum, max_sum);
  36. 	}
  37. 	cout<<max_sum;
  38. 	return 0;
  39. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
https://ideone.com/IA1J7A
language:
C++ (gcc 8.3)
created:
3 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!