二维数组最大连通子数组之和

问题：返回一个二维整数数组中最大联通子数组的和

思路：把数按行分成几个一维数组，对于该一维数组，求出他们的最大连续数组之和，并且记录下最大连续数组的第一位和最后一位的位置，之后判断几个一维数组的最大连续数组的位置是否相接或包括（如，第一行是1和4，第二行是3和5，这样就相连）。最后在加上没有包括的正数（必须在上一行的最大连续数组的第一位和最后一位的位置之间）。输出之前之和就行。

缺陷：数组中不可以出现0，现在的程序只能解决最大连续数组相连的，还不能解决不相连的，对于最后今加上剩余的正数，只会加上与第一行重合的，第三行以及以下的行并不加上前一步加上的第二行的正数。

代码：

#include<iostream>
using namespace std;

int Max(int n,int a[],int *smark,int *mmark)
{
	int b[100]={0};
	int i,sum1=0,max1=0;
	for(i=0;i<n;i++)
	{
		if(sum1<0)
		{
			sum1=a[i];
		}
		else
		{
			sum1=sum1+a[i];
		}
		b[i]=sum1;
	}
	max1=b[0];
	for(i=0;i<n;i++)
	{
		if (max1<b[i]) 
         {
             max1= b[i];
             *mmark = i;
         }
	}
	 for (i = *mmark;i >= 0;i--) 
    {
        if (b[i] == a[i]) 
        {
             *smark = i;
             break;
        }
    }
	 return max1;
}

void main()
{
	int m,n,i,j,smark,mmark,t2;
	int sum,max;
	int up[100],down[100],t[100];
	int a[100][100],b[100];
	cout<<"输入二维数组的行和列";
	cin>>m>>n;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}

	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			b[j]=a[i][j];
		}
		sum=Max(n,b,&smark,&mmark);
		up[i]=smark;                                    
        down[i]=mmark;
        t[i]=sum;

	}
	t2=t[0];
    for(i=0;i+1<m;i++)
    {
        if(up[i]<=down[i+1] && down[i]>=up[i+1])
        {
            t2+=t[i+1];
        }
		 for(j=up[i];j<up[i+1];j++)
        {
			if(a[i+1][j]>0) t2+=a[i+1][j];                   //判别独立正数
        }

	}
	 cout<<t2<<endl;

}

　　

截图：

总结：之前认为二维数组的题大概都会了，坐完这道题，发现我还差很多，就行以后的学习之路，永无止境，永远没有尽头