最大子段和输出有关问题

最大子段和输出问题
我用了三种方法求最大子段和，但我们老师要求把最大子段也要输出来，我改了两个小时没头绪，求高手解答
#include<iostream>
using namespace std;
#define Max 20
int Check(int r[],int low,int high)//判断是否每个整数都为负数
{
int i;
for(i=low;i<=high;i++)
if(r[i]>=0) break;
if(i==high+1) return 0;
else return 1;
}
int Sum(int r[],int low,int high)//求元素总和
{
int i,sum=0;
for(i=low;i<=high;i++)
sum+=r[i];
return sum;
}
int MaxSum1(int r[],int low,int high)//蛮力法
{
int i,j,sum=0;
if(!Check(r,low,high)) return 0;
for(i=low;i<=high;i++)
for(j=i;j<=high;j++)
if(Sum(r,i,j)>sum) sum=Sum(r,i,j);  
return sum;
}
int MaxSum2(int r[],int low,int high)//分治法
{
int i,sum=0,n,sum1,sum2;
if(low==high)  
{
if(r[low]<0) sum=0;
else sum=r[low];
}
else
{
n=(low+high)/2;
sum1=MaxSum2(r,low,n);
sum2=MaxSum2(r,n+1,high);
int s1=0,a=0;
for(i=n;i>=low;i--)
{
a+=r[i];
if(a>s1) s1=a;
}
int s2=0,b=0;
for(i=n+1;i<=high;i++)
{
b+=r[i];
if(b>s2) s2=b;
}
sum=s1+s2;
if(sum1>sum) sum=sum1;
if(sum2>sum) sum=sum2;
}
return sum;
}
int MaxSum3(int r[],int low,int high)//动态规划
{
int i,b=0,sum=0;
for(i=low;i<=high;i++)
{
if(b>0)
b+=r[i];
else
b=r[i];
if(b>sum) sum=b;
}
return sum;
} 
void main()
{
int r[Max],n,i;
cout<<"请输入数组元素个数：";  
cin>>n;
cout<<"请输入这"<<n<<"个元素："<<endl;
for(i=0;i<n;i++)
cin>>r[i];
cout<<"最大字段和分别如下："<<endl;
cout<<"蛮力法的结果是："<<MaxSum1(r,0,n-1)<<endl;
cout<<"分治法的结果是："<<MaxSum2(r,0,n-1)<<endl;
cout<<"动态规划的结果是："<<MaxSum2(r,0,n-1)<<endl;
}

[解决办法]
http://acm.hdu.edu.cn/showproblem.php?pid=1003
下面是杭电 1003 的代码，也是求最大子段和，要求输出最大子段，用动态规划做的，楼主参考下。。

C/C++ code

#include"stdio.h"#define M 100000int main(){int i,j,k,l,t,x,c,max,T,N;int a[M],b[M];scanf("%d",&T);for(i=1;i<=T;i++){scanf("%d",&N);for(j=1;j<=N;j++)scanf("%d",&a[j]);b[1]=a[1];for(k=2;k<=N;k++)if(b[k-1]>0)b[k]=b[k-1]+a[k];elseb[k]=a[k];max=b[1];t=1;for(l=1;l<=N;l++)if(max<b[l]){max=b[l];t=l;}x=1;for(c=t;c>=1;c--)if(b[c-1]<0){x=c;break;}printf("Case %d:\n",i);printf("%d %d %d\n",max,x,t);if(i<T)printf("\n");}return 0;}