Max Sum

   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, a;
  10         int max_sum = INT_MIN;
  11         int max_start, max_end;
  12         int start, end, sum;
  13         scanf("%d", &n);
  14 
  15         start = 0;
  16         sum = 0;
  17         for(end = 0; end < n; end++) {
  18             scanf("%d", &a);
  19             sum += a;
  20             if(sum > max_sum) {
  21                 max_sum = sum;
  22                 max_end = end;
  23                 max_start = start;
  24             }
  25             if(sum < 0) {
  26                 start = end + 1;
  27                 sum = 0;
  28             }
  29         }
  30         printf("Case %d:\n%d %d %d\n", t, max_sum, max_start+1, max_end+1);
  31         if(t != T)
  32             printf("\n");
  33     }
  34 }