連通最大子數組和（結對開發）

題目:傳回一個二維數組中最大子數組的和（連通性）

合作夥伴：張江鵬    部落格位址：http://home.cnblogs.com/u/gaara-zhang/

設計思路：把數按行分成幾個一維數組，對于該一維數組，求出他們的最大連續數組之和，并且記錄下最大連續數組的第一位和最後一位的位置，之後判斷幾個一維數組的最大 連續數組的位置是否相接或包括（如，第一行是1和4，第二行是3和5，這樣就相連）。最後在加上沒有包括的正數（必須在上一行的最大連續數組的第一位和最 後一位的位置之間）。輸出之前之和就行。

#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;
  
}