题目大意:
给定一段数字序列(有正负),求最大的子串和以及该子串的始末位置。
解决:
使用在线处理方法处理最大子串和,时间复杂度O(N)
设置临时最大和sum,最大和max
遍历数字序列将a[i]累加到sum
1.若sum > max, 则更新max值和子串尾下标
2.若sum <= max, 则继续向后累加
遍历过程中,当发现sum < 0时,使sum=0并将子串起点下标后移
附:因为序列中每个数字仅被处理一次,所以复杂度O(N)
代码
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 |
#include <stdio.h> int a[100010]; int main(){ int T, N, cas = 1; scanf("%d",&T); while(T--){ scanf("%d",&N); int start=1,end=1,temp=1; int sum = 0; int max = -1001; for(int i = 1; i <= N; ++i){ scanf("%d",&a[i]); sum += a[i]; if(sum > max){ // 只有和更大,终点才后移,起点不变 max = sum; start = temp; end = i; } if(sum < 0){ sum = 0; temp = i+1; // 以刚累加的元素的下一元素为新起点 } } printf("Case %d:\n",cas++); printf("%d %d %d\n",max, start, end); if(T > 0) printf("\n"); } return 0; } |
文章评论