1 /*written by czk*/
   2 /*O(n^2), Time Limit Exceed*/
   3 #include <stdio.h>
   4 #include <limits.h>
   5 int main() {
   6     int T, t;
   7     scanf("%d", &T);
   8     for(t = 1; t <= T; t++) {
   9         int n, i;
  10         short a[100000];
  11         int max_sum = INT_MIN;
  12         int max_start, max_end;
  13         int start, end;
  14         scanf("%d", &n);
  15         for(i = 0; i < n; i++)
  16             scanf("%d", &a[i]);
  17         for(start = 0; start < n; start++) {
  18             int sum = 0;
  19             for(end = 0; end < n; end++) {
  20                 sum += a[end];
  21                 if(sum > max_sum) {
  22                     max_sum = sum;
  23                     max_start = start;
  24                     max_end = end;
  25                 }
  26             }
  27         }
  28         printf("Case %d:\n%d %d %d\n", t, max_sum, max_start+1, max_end+1);
  29         if(t != T)
  30             printf("\n");
  31     }
  32 }

   1 /*written by czk*/
   2 /*O(n), AC*/
   3 #include <stdio.h>
   4 #include <limits.h>
   5 int main() {
   6     int T, t;
   7     scanf("%d", &T);
   8     for(t = 1; t <= T; t++) {
   9         int n, i;
  10         short a[100000];
  11         int max_sum = INT_MIN;
  12         int max_start, max_end;
  13         int start, end, sum;
  14         scanf("%d", &n);
  15         for(i = 0; i < n; i++)
  16             scanf("%d", &a[i]);
  17 
  18         start = 0;
  19         sum = 0;
  20         for(end = 0; end < n; end++) {
  21             sum += a[end];
  22             if(sum > max_sum) {
  23                 max_sum = sum;
  24                 max_end = end;
  25                 max_start = start;
  26             }
  27             if(sum < 0) {
  28                 start = end + 1;
  29                 sum = 0;
  30             }
  31         }
  32         printf("Case %d:\n%d %d %d\n", t, max_sum, max_start+1, max_end+1);
  33         if(t != T)
  34             printf("\n");
  35     }
  36 }