最大连续子序列 1231

解法一：记录下标

#include <stdio.h>
#include<iostream>
using namespace std;
 
#define N 10001
int a[N];
 
int main()
{
    int n,max,start,end;
    while(cin>>n && n)
    {
        max=0x80000000;
        int sum=0;
        int tempStart=1;
        for(int i=1;i<n +1;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            if(sum>max)
            {
                max=sum;
                start=tempStart;
                end=i;
            }
            if(sum < 0)
            {
                tempStart=i+1;
                sum=0;
            }
        }
        if(max>=0)
        {
            cout<<max<<' '<<a[start]<<' '<<a[end]<<endl;
        }
        else
        {
            cout<< 0<<' '<<a[1]<<' '<<a[n]<<endl;
        }
    }
    return 0;
}

解法二：把相加的值放入一个数组，再遍历找出最大的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXK 10002
int n[MAXK],dp[MAXK],start[MAXK];
int main()
{
	int K;
	while(cin>>K&&K!=0)
	{
		for(int i=0;i<K;i++)
			scanf("%d",&n[i]);//存入到数组n中
		dp[0] = n[0];
		start[0] = n[0];
		for(int i=1;i<K;i++)
		{
			if(dp[i-1]+n[i]>n[i])//加多一个大于后一个
			{
				dp[i] = dp[i-1]+n[i];
				start[i] = start[i-1];
			}else{//小于后一个
				dp[i] = n[i];
				start[i] = n[i];
			}
		}
		int sum,pos;
		sum = dp[0];
		pos = 0;
		for(int i=1;i<K;i++){
			if(dp[i]>sum)
			{
				sum = dp[i];
				pos = i;
			}
		}
		if(sum<0)
			cout<<"0 "<<n[0]<<' '<<n[K-1]<<endl;
		else
			cout<<sum<<' '<<start[pos]<<' '<<n[pos]<<endl;
	}
	return 0;
}

解法一比较巧妙