求最大子序列和，并确定其位置，高效算法的话DP和分治了
但是还要确定子序列的位置，即第几个元素到第几个元素
我用DP求出和还有位置，用分治也求出了和，但是求不出位置，一般情况可以确定，但是一些特殊情况就错了

先贴分治求最大子序列和的代码

//最大连续和子序列
//用分治递归法来求
#include <stdio.h>
#include <string.h>
int a[100010];
int k,j;
int flag;

int SUM(int x ,int y)
{
    int sum1,sum2,max;  int m;  int temp,L,R,i;
    if(y-x==1)  {p=q=x; return a[x]; }
   
   
    m=x+(y-x)/2;
    sum1=SUM(x,m); 
    sum2=SUM(m,y); 
    if(sum1>=sum2)  max=sum1; 
    else            max=sum2; 
   
    temp=0;L=a[m-1];k=m-1;   //p3是用于记录子序列的头
    for(i=m-1; i>=x; i--)    
    {   temp+=a[i]; if(temp>=L) L=temp;   }
   
    temp=0;R=a[m];j=m;      //q3是用于记录子序列的尾
    for(i=m; i<y; i++)       
    {   temp+=a[i]; if(temp>=R) R=temp; j=i;   }
   
    if(max>(L+R))  return max; 
    else           return (L+R); 
}

int main()
{
    int n; int i;  int max;  int t,T;
    scanf("%d",&T);
    for(t=1; t<=T; t++)
    {
        scanf("%d",&n);
        for(i=1; i<=n; i++)  scanf("%d",&a[i]);
        max=SUM(1,n+1);
        printf("Case %d:\n",t);
        printf("%d %d %d\n",max,p,q);
        if(t!=T)  printf("\n");
    }
    return 0;
}

确定位置dp也够了

又是最大子段和...你们慢慢讨论

后来我推导出来，只要把MAX定义为全局变量，把原来的int 函数改为 void 然后再定义两个begin end 变量来记录子序列的位置………………
原来很简单，想通了什么都简单………………