寻找数串中连续最大整数和且最大长度的子串
输入示例:
1000 -100 200 -200 100 -100 10 90
输出结果:
1100
分析:
分治法解决问题非常方便,依然分为三种情况:a[1], a[2]......a[mid-1], a[mid], a[mid+1]......a[n-1], a[n]
1.最大和数串位于a[mid]左边数串中;
2.最大和数串位于a[mid]右边数串中;
3.最大和数串包括a[mid]。
明显地,情况1,2是原问题的子问题,但情况3则并不是原问题子问题,因为它有条件限制,所以我们需要另外求解。
#include <stdio.h>
#include <stdlib.h> struct ansmax{
int lindex;
int hindex;
int summax;
};
typedef struct ansmax ans; int find_cross_max(int *data, int mid, int lindex, int hindex, ans* max){ //计算经过中间点的最大和数串
int leftmax, rightmax;
int maxtemp,maxt;
int k; for(k=mid, maxtemp=0, maxt=-100000, leftmax=mid; k>=lindex; k--){ //maxt=负无穷
maxtemp += *(data+k);
if(maxtemp>maxt){
maxt=maxtemp;
leftmax=k;
}
}
for(k=mid, maxtemp=0, maxt=-100000, rightmax=mid; k<=hindex; k++){
maxtemp += *(data+k);
if(maxtemp>maxt){
maxt=maxtemp;
rightmax=k;
}
} //返回经过最大值
for(k=leftmax, max->summax=0; k<=rightmax; k++){
max->summax += *(data+k);
max->lindex = leftmax;
max->hindex = rightmax;
}
} void findmax(int *data, int lindex, int hindex, ans* max){
ans crossmax;
ans leftmaxsum, rightmaxsum;
int mid; if(lindex==hindex){
max->hindex=hindex;
max->lindex=lindex;
max->summax=*(data+lindex);
return;
}
mid=(lindex+hindex)/2;
if(mid-1>=lindex)
findmax(data, lindex, mid-1, &leftmaxsum);
else
leftmaxsum.summax = -100000; //应该设置为负最大值
if(mid+1<=hindex)
findmax(data, mid+1, hindex, &rightmaxsum);
else
rightmaxsum.summax = -100000; //应该设置为负最大值
find_cross_max(data, mid, lindex, hindex, &crossmax);
if(leftmaxsum.summax>rightmaxsum.summax&&leftmaxsum.summax>crossmax.summax){
max->summax = leftmaxsum.summax;
max->lindex = leftmaxsum.lindex;
max->hindex = leftmaxsum.hindex;
}
else if(rightmaxsum.summax>leftmaxsum.summax&&rightmaxsum.summax>crossmax.summax){
max->summax = rightmaxsum.summax;
max->lindex = rightmaxsum.lindex;
max->hindex = rightmaxsum.hindex;
}
else{
max->summax = crossmax.summax;
max->lindex = crossmax.lindex;
max->hindex = crossmax.hindex;
}
} int main(void){
int datalen;
int *dataptr;
int k, sum1, sumtemp1, sum2, sumtemp2;
int *maxtail, *maxhead, *curptr;
ans myans; printf("input datalen:"); scanf("%d",&datalen);
if(datalen<=0) return 0;
if((dataptr=(int*)malloc(sizeof(int)*datalen))==NULL){
printf("malloc failed\n");
exit(0);
}
for(k=0; k<datalen; k++){
printf("input data %d/%d:", k+1, datalen);
scanf("%d", dataptr+k);
} findmax(dataptr, 0, datalen-1, &myans);
for(k=myans.lindex; k<=myans.hindex; k++){
printf("%d ", *(dataptr+k));
}
printf("\n%d\n", myans.summax); system("pause");
return 0;
}
由JULY博客提供的方法,可以大大简化代码的时间复杂度,变为线性复杂度O(n),且空间复杂度为O(1)
其代码为:
#include <stdio.h>
#include <stdlib.h> int maxsum(int a[],int n)
{
int max=a[0]; //全负情况,返回最大数
int sum=0;
int j;
for(j=0;j<n;j++)
{
if(sum>=0) //如果加上某个元素,sum>=0的话,就加
sum+=a[j];
else
sum=a[j]; //如果加上某个元素,sum<0了,就不加,这里就不清零了
if(sum>max)
max=sum;
}
return max;
} int main(void){
int n, k;
int *a; scanf("%d", &n);
a = (int*)malloc(sizeof(int));
for(k=0; k<n; k++){
scanf("%d", a+k);
} printf("%d\n", maxsum(a,n)); system("pause");
return 0;
}