P1115 最大子段和
思路分析
一个长度为 n 的序列有很多长短不一的连续子段，子段的位置有前后之分（即子段的第一个值的位置有前后之分）。可以定义一个数组 a[ ] 存放序列的值；数组 b[ ] 存放子段和，下标表示子段的位置，初始化为 n 个长度为 1 的子段，即与序列一样；从第二个位置开始一直到最后一个位置，如果这个子段的第一个值加上上一个位置的子段和大于它本身，则将此和赋值给该子段和，成为一个更大的新子段，公式表示为：b[ i ] = max(a[ i ], a[ i ] + b[ i - 1])；求出所有子段和的最大值即为最大的子段和；
注意事项
由题可知：对于40%的数据，保证 n <= 2 * 10^3，对于100% 的数据，保证 1 <=n <= 2 * 10^5，- 10^4 <= a[ i ] <= 10^4；所以定义数组为a[ 200005 ], b[ 200005 ]；求子段和的最大值时需事先定义一个足够小的数来比较，或直接用序列中的某个值来比较，否则可能得到一个比所有子段和更大的答案；
代码实现
#include <stdio.h>
int max(int, int);
int main(){
int n
, i
, M
;
int a
[200005], b
[200005];
scanf("%d", &n
);
for(i
= 0; i
< n
; i
++){
scanf("%d", &a
[i
]);
b
[i
] = a
[i
];
}
M
= a
[0];
for(i
= 1; i
< n
; i
++){
b
[i
] = max(a
[i
], b
[i
-1] + a
[i
]);
M
= max(M
, b
[i
]);
}
printf("%d", M
);
return 0;
}
int max(int x
, int y
){
return x
> y
? x
: y
;
}
