- #include
- #include
- using namespace std;
- voidMaxIntArray(inta[],int&max,int&begin,int&end,int n);
- //先将二维数组按行分成n个一维数组,求出每个一维数组最大子数组和,并记录最大子数组和的首末位置,在通过首末位置判断是否联通
- void main()
- {
- intn,m;//n行m列cout<<"请输入二维数组的行数和列数:"<<endl;
- cin>>n>>m;
- inta[100][100];
- intb[100];
- cout<<"输入该二维数组"<<endl;
- for(inti=0;i)
- for(intj=0;j)
- cin>>a[i][j];
- //分块
- intMax[100];
- intBegin[100];
- intEnd[100];
- for(inti=0;i)
- {
- //按行分组
- for(intj=0;j)
- {
- b[j]=a[i][j];
- }
- MaxIntArray(b,Max[i],Begin[i],End[i],m);
- }
- intmax=Max[0];
- for(inti=0;i)
- {
- if((Begin[i]<=End[i+1]&&Begin[i]>=Begin[i+1])||(End[i]<=End[i+1]&&End[i]>=Begin[i+1]))
- {
- max=Max[i+1]+max;
- }
- else
- {
- //如果不能直接连通,判断代价是否合适
- if(Begin[i]>End[i+1])
- {
- intt = Begin[i]-End[i+1];
- ints = Begin[i];
- inttemp=0;
- for(intk=0;k)
- {
- temp+=a[i+1][s-k];
- }
- if(temp+Max[i+1]>0)
- max=temp+Max[i+1];
- }
- if(End[i]])
- {
- intt = Begin[i+1]-End[i];
- ints = End[i];
- inttemp=0;
- for(intk=0;k)
- {
- temp+=a[i+1][s+k];
- }
- if(temp+Max[i+1]>0)
- max=temp+Max[i+1];
- }
- }
- }
- cout<<"最大子数组块的值为:"<endl;
- }
- //计算一维最大子数组,并返回起始位置的函数
- voidMaxIntArray(inta[],int&max,int&begin,int&end,int n)
- {
- intMax[100];
- Max[0] = 0;
- inti = 0;//数组下标
- intj = 0;//最大值数组下标
- inttemp=0;//中间变量
- //记录子数组的起始位置和末位
- intBg[100]={-1,-1,-1,-1,-1};
- intEd[100];
- while(i<n){
- if(temp+a[i]>=Max[j])
- {
- temp=temp+a[i];
- Max[j]=temp;
- if(Bg[j]==-1)
- Bg[j]=i;
- Ed[j]=i;
- i++;
- }
- else if(temp+a[i]0)
- {
- temp=temp+a[i];
- i++;
- }
- else if(temp+a[i]<=0)
- {
- i++;
- j++;
- Max[j]=0;
- temp=0;
- }
- }
- max = Max[0];
- intq=0;
- for(intk=0;k<=j;k++){
- if(Max[k]>max)
- {
- max=Max[k];
- q=k;
- }
- }
- begin=Bg[q];
- end=Ed[q];
- }
来源: http://www.bubuko.com/infodetail-2050752.html