package erweishuzu;
 
import java.util.Scanner;
public class shuzu {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
         
             int a[][]=new int[20][20];
             Scanner str=new Scanner(System.in);
             System.out.print("请输入二维数组的行数列数:");
             int index=str.nextInt();
             int length=str.nextInt();
              
             int y=0;
             System.out.println("请输入数组:");
             for(int i=0;i<index;i++)
             {
                 for(int j=0;j<length;j++)
                 {
                    a[i][j]=str.nextInt();
                 }
             }
             int s=sum(a,length,index);
             System.out.println("最大连通子数组和:"+s);
    }
    public static int max2(int arry[],int length)
    {
            int total=0;
            int sum=arry[0];
            int minsum=arry[0];
            for(int i=1;i<length;i++)
            {
                if(sum>0)
                {
                    sum=arry[i];
                }
                else
                {
                    sum=sum+arry[i];
 
                }
                if(minsum>=sum)
                {
                    minsum=sum;
                }
                total=total+arry[i];
            }
            total=total+arry[0];
            minsum=total-minsum;
 
            return minsum;
    }
    public static int max1(int arry[],int length)  
    {
            int sum=arry[0];
            int maxsum=arry[0];
            for(int i=1;i<length;i++)    
            {
                if(sum<0)
                {
                    sum=arry[i];
                }
                else
                {
                    sum=sum+arry[i];
 
                }
                if(maxsum<=sum)
                {
                    maxsum=sum;
                }
            }
            return maxsum;
    }
    public static int sum(int a[][],int length,int num1)
    {   
          int y=0;
          int d[]=new int[20];
          int e[]=new int[100];
          int c[][]=new int[100][20];
          c[0][0]=0;
          int p=0;
          int[] b=new int[100];
          b[0]=0;
          for(int j=0;j<num1;j++)
          {
              for(int t=j;t<num1;t++)
              {
                  for(int i=0;i<length;i++)
                  {
                      b[i]=b[i]+a[t][i];
                      c[p][i]=b[i];
                  }
                  p=p+1;
              }
              for(int o=0;o<100;o++)
              {
                  b[o]=0;
              }
          }
          for(int l=0;l<p;l++)
          {
 
              for(int u=0;u<length;u++)
              {
                  d[u]=c[l][u];
              }
              e[y++]=max1(d,length);
              e[y++]=max2(d,length);
 
          }
          int Max=e[0];
          for(int i=0;i<y;i++)
          {
 
              if(e[i]>=Max)
             {
                 Max=e[i];
             }
          }
        return Max;
    }
     
     
}