最大子段和用分治的话符合记录字段的起始和结束位置？
用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;
}
