思路 子序列最大和

看到好像没人用我这方法做，多写写

我用a记录初始编号，b记录终止编号，fg用来记录是否数组数字全为负数，max记录当前数组内最大值，aa记录当前数组内最大数的位置，c来更新有效初始位置（原因下面说）maxsum记录当前算得最大奖励值，sum记录当前算得奖励值 首先将所有数读入，判断所有数是否都为负数，如果是的话就直接输出数组最大值所在位置，因为负数都越加越小

当所有数不都为负数时，设a[i]为和最大序列的起点，如果a[i]是负的，那么它不会是 和最大子序列的起点，可以得到：负的子序列也不会是 和最大子序列 的前缀。

所以在循环中用b一直更新当前 和最大子序列 的终点坐标，用a更新其起点坐标

注意：当此时子序列和为负数时起点要向后移，再继续向后找，但之前记录的可能正确起点就要先用c来储存

最后分情况输出答案即可

代码

#include<stdio.h>
int main()
{
	int a=1,b=1,n,s[100005]={0},fg=0,max=-1000000,aa,c=1;
	int maxsum = 0,sum;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		if(s[i]>0)fg=1;
		if(s[i]>max)max=s[i],aa=i;
	}
	for(int i=1;i<=n;i++)
	{
			sum+=s[i];
			if(sum>maxsum)
			{
				b=i;
				maxsum=sum;
				c=a;
			}
			else if(sum<0)
			{
				a=i+1;
				sum=0;
			}
	}
	if(fg==1)
	printf("%d\n%d\n%d",c,b,maxsum);
	else
	printf("%d\n%d\n%d",aa,aa,max);
        return 0;
 }