求二维数组的最大子数组

浏览数：16 / 时间：2015年06月08日

一、题目：

n返回一个二维整数数组中最大子数组的和。

二、要求：

n输入一个二维整形数组，数组里有正数也有负数。

n二维数组中连续的一个子矩阵组成一个子数组，每个子数组都有一个和。

n求所有子数组的和的最大值。要求时间复杂度为O(n)。

三、程序源码：

import java.util.Random;
import java.util.Scanner;

public class dd {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
                System.out.println("请输入数组的行数和列数：");
                Scanner sc=new Scanner(System.in);
                int n=sc.nextInt();
                int m=sc.nextInt();
                int a[][]=new int[n][m];
                Random rand=new Random();
                int Sum=0;
                int N=0;
                int i=0;
                int e=0;
                System.out.print("请输入数字范围：");
                int m1=sc.nextInt();
                int m2=sc.nextInt();
                for(e=0;e<m;e++)
                {
                    for(i=0;i<n;i++)
                    {
                        a[i][e]=(int) (m1+Math.random()*(m2-m1+1));
                        System.out.print(a[i][e]+"  ");
                    }
                    System.out.println();
                }
                int M=a[0][0];
                for(e=0;e<m;e++)
                {
                    int y=e;
                    do
                    {
                       for(i=0;i<n;i++)
                       {
                           for(int u=e;u>=y;u--)
                           {
                               Sum=Sum+a[i][u];
                           }
                            N=N+Sum;
                            if(N>=M)
                            {
                                M=N;
                            }
                            if(N<0)
                            {
                                N=0;
                            }
                            Sum=0;
                       }
                       y--;
                       N=0;
                    }while(y>=0);
                }
                System.out.println("最大:"+M);
    }
      
}