Question

C++求数组最大子数组，请教这个哪里出错了。 要求数组大小1<=n<=5000 元素大小[-5000,5000]

求最大子数组的元素的和，就是一个值。 比如1 -1 1 1 -1 那和就是2

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
//求最大子集
/*这是算法导论中,线性时间规划的一道题
线性时间实现基于这样的思路：
如果a[1..j]已经得到了其最大子数组，那么a[1..j+1]最大子数组只能是两种情况
（1）a[1..j+1]的最大子数组就是a[1..j];
（2）a[1..j+1]的最大子数组是a[i..j+1],1<=i<=j;
那么，如何求得所谓的（2）中的a[i..j+1]呢？
首先需要承认这样的事实，如果一个数组a[p..r]求和得到负值，那么数组a[p..r+1]的最大子数组肯定不会是a[p..r+1]，因为a[p..r]+a[r+1]<a[r+1].
在以上程序中，我们用temp存储所谓的a[p..r]，只要a[p..r]的求和是负值，那么从下一个a[r+1]值开始，temp重新从零开始求和，只要temp > summax,就更新summax,这样，我们一次遍历后，就能得到最大的summax,接下来，我们证明该算法是有效的
证明：
对于所有数组元素，这样的元素对数组进行划分，如果加上该元素之前temp>0且temp+a[i]<0，那么该元素a[i]是一个边界，这样，数组会形成好多段，每段结束元素都满足temp>0且temp+a[i]<0.所以我们能得到多个划分块a[p..q]，每个划分快的和是负值，划分块有这样的性质，对任意p<=i<q,显然，sum(a[p..i])>=0且sum(a[i..q]）<0;
我们要证明
（1）最大子数组一定在划分块之内
证明：
根据划分快性质，容易证明，只要子数组横跨多个划分快，其求和值必定小于某个单独的划 分快中的数组求和。
（2）一定存在首元素以划分块的首元素开始的最大子数组。
证明：
对于某个划分快a[p..q],假设存在a[i..j],其中p<i<=j<q,那么根据划分块性质，a[p..i-1]+a[i..j]>=a[i..j]必定成立,得证。
所以，经历一次遍历，对于每个划分块，从首元素开始求和，得到最大值更新summax,一定能够得到最大子数组的值。
*/
int maxsubset(int *a,int l,int r) //l数组起始索引 r终止索引
{
int i,
temp=0,
summax=INT_MIN; //包含在limits.h中
for(i=l;i<=r;i++)
{
temp+=a[i];
if(temp > summax) summax=temp;
if(temp < 0) temp=0;
}
return summax;
}
int main(void)
{
int a[]={3,-1,2,5,-3,4,-6,-7,1,8,-3,5,9};
int len = sizeof(a)/sizeof(int);
printf("the maxsubset:%d\n",maxsubset(a,0,(len-1)));
}

Answer 2

你的意思是求，：数组子数组中，和最大的数组？

追问

和最大的子数组的和，求这个值。

追答

//我想我下面写的应该是对的吧！
//你可以去百度一下有联机算法，我的这个不是
int sum=0,maxsum=0;
int begin,end;//开始
for(int i=0;imaxsum)
{
begin=i;
end=j;
maxsum=sum;
}
}
sum=0;
}
int i=begin;
int b[100]={0};
int m=0;
while(i<=end)
{
b[m]=a[i];
m++;
i++;
}