1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <stdio.h>
#define MAX_LEN 100000UL
int max_subsq(int *array, unsigned int size, unsigned int *start, unsigned int *end)
{
int max_sum = -2000, sum = 0;
int curstart = *start = 0;
unsigned int i;
for (i = 0; i < size; i++){
if (sum < 0){
sum = array[i];//丢弃之前的子串
curstart = i; //将当前位置作为新的起始位置
} else {
sum += array[i];
}
if (sum > max_sum){
max_sum = sum;
*start = curstart;
*end = i;
}
}
return max_sum;
}
int main(void)
{
int A[MAX_LEN];
int i = 0, round, n, max;
unsigned int start, end;
freopen("/Users/RichardLu/Code/C++/Algorithm/largeNumberSort/largeNumberSort/largeNumberSort/testcase.in", "r", stdin);
freopen("/Users/RichardLu/Code/C++/Algorithm/largeNumberSort/largeNumberSort/largeNumberSort/testcase.out", "w", stdout);
scanf("%d", &round);
while (i++ < round)
{
scanf("%d", &n);
for (int j = 0; j < n; j++){
scanf("%d", &A[j]);
}
max = max_subsq(A, n, &start, &end);
printf("Case %d:\n", i);
printf("%d %d %d\n", max, start + 1, end + 1);
if (i != round) printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}
|