最大子段和用分治的话符合记录字段的起始和结束位置？
用DP做过。
如下是网上常用的分治求最大子段和的代码，但是怎么记录子段的起始和结束位置？

#include<stdio.h>

int maxSubNumber(int *a,int left,int right)  
{
    int sum = 0;  
    int i,j;
    if(left == right)  
    {
        sum = a[left];   
    }
    else
    {
        int mid = (left+right)/2;        
        int leftsum = maxSubNumber(a,left,mid);     
        int rightsum = maxSubNumber(a,mid+1,right);   
        int s1 = a[mid];
        int temp = 0;
        for(i=mid;i>=left;i--) 
        {
            temp = temp+a[i];
            if(temp>s1)
            {
                s1 = temp;
            }
        }
        int s2 = a[mid+1];
        temp = 0;
        for(j=mid+1;j<=right;j++)
        {
            temp = temp + a[j];
            if(temp>s2)
            {
                s2 = temp;
            }
        }
        int s = s1 + s2;  
        sum = s;

        if(leftsum>s)
        {
             sum = leftsum;
        }
        if(rightsum>s)
        {
             sum = rightsum;
        }
    }
    return sum;
}

[解决办法]

#include<stdio.h>
 
int maxSubNumber(int *a,int left,int right,int *st, int *end)  
{
    int sum = 0;  
    int i,j;
    if(left == right)   
 
    {
        sum = a[left];   
        *st = *end = left;  
    }
    else
    {
        int mid = (left+right)/2, l_st,l_end, r_st,r_end;        
        int leftsum = maxSubNumber(a,left,mid, &l_st,&l_end);     
        int rightsum = maxSubNumber(a,mid+1,right, &r_st, &r_end);   
        int s1 = a[mid];
        int temp = 0;
        for(i=mid;i>=left;i--) 
        {
            temp = temp+a[i];
            if(temp>s1)
            {
                s1 = temp;
                *st = i;
            }
        }
        int s2 = a[mid+1];
        temp = 0;
        for(j=mid+1;j<=right;j++)
        {
            temp = temp + a[j];
            if(temp>s2)
            {
                s2 = temp;
                *end = j;
            }
        }
        int s = s1 + s2;  
        sum = s;
 
        if(leftsum>s)
        {
             sum = leftsum;
             *st = l_st, *end = l_end;
        }
        if(rightsum>s)
        {
             sum = rightsum;
             *st = r_st, *end = r_end;
        }
    }
    return sum;
}