fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int kadaneAlgo(int a[], int n) {
  5. 	// for Non linear
  6. 	int cs=0,ms=0;
  7. 	for(int i=0; i<n; i++) {
  8. 		if(cs < 0) {
  9. 			cs=0;
  10. 		}
  11. 		cs = cs + a[i];
  12. 		if(cs > ms) {
  13. 			ms = cs;
  14. 		}
  15. 	}
  16. 	return ms;
  17. }
  18.  
  19. int circularSum(int a[], int n) {
  20. 	// for Circular fashion 
  21. 	int max_kadane = kadaneAlgo(a,n);
  22. 	int max_sum = 0;
  23. 	for(int i=0; i<n; i++) {
  24. 		max_sum += a[i];
  25. 		a[i] = -a[i];
  26. 	}
  27.  
  28. 	// compute the maxSum means the minimum sum of the elements 
  29. 	 max_sum =  max_sum + kadaneAlgo(a,n);
  30.  
  31. 	 return (max_sum > max_kadane) ? max_sum : max_kadane;
  32. }
  33.  
  34.  
  35. int main(int argc, char const *argv[])
  36. {
  37. 	int t,c=0,n;
  38. 	cin >> t;
  39. 	int arr[10000];
  40. 	while(c<t){
  41. 		cin >> n;
  42. 		for(int i=0; i<n; i++) {
  43. 			cin >> arr[i];
  44. 		}
  45. 		cout << circularSum(arr,n);
  46. 		c++;
  47. 	}
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
1
7 
8 -8 9 -9 10 -11 12
stdout
copy 
22
https://ideone.com/nzT6yE
language:
C++14 (gcc 8.3)
created:
6 years 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!