最小矩阵和

很久很久以前的代码，在某个角落找到，贴了上来， 在杭电acm1081上可以ac，来源应该是Greater New York 2001 貌似作为中南赛区ACM竞赛题 问题描述 【Description】 Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. As an example, the maximal sub-rectangle of the array: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 is in the lower left corner: 9 2 -4 1 -1 8 and has a sum of 15. 【Input】 The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127]. 【Output】 Output the sum of the maximal sub-rectangle. 【Sample Input】 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 【Sample Output】 15 下面的中文来自：http://blog.csdn.net/hym666/archive/2010/08/17/5818591.aspx 此文章处有C++的解答 题目描述： 在一个大的方阵中找出一个子方阵，这个子方阵是所有子方阵和中的最大的一个 问题分析： 问题可以回归到一个数列中的连续字数列的和的最大值。 即把每一行看成一个数列。把每一列转换成一个数。 当然每一列也是一个数列，有很多的连续子数列。所有会有很多中情况。可穷举各种数列来构造一个行向的数列。 再用动态规划计算每一行的最大值，再在各行中选取最大的作为题目的解。 【代码】

import java.util.*;

public class Main {

       /**
        * @param args
        */

       public static int maxSum(int[] b, int n){

              int max = b[0], sum = 0;

              for (int i = 1; i < n ; i++ ){
                     if (max > 0)
                            max += b[i];
                     else
                            max = b[i];

                     if (max > sum)
                            sum = max;
              }
              return sum;
       }

       public static int maxTotal(int[][] a, int n){

              int max = 0;
              int[] b = new int[n];

              for (int i = 0; i < n; i++){
                     for (int j = 0; j < n; j++)
                            b[j] = a[i][j];

                     int sum = maxSum(b, n);

                     if (sum > max)
                            max = sum;

                     for (int j = i + 1; j < n; j++){
                            for (int k = 0; k < n; k++)
                                   b[k] += a[j][k];

                            sum = maxSum(b, n);
                            if (sum > max)
                                  max = sum;
                     }
              }
              return max;
       }

       public static void main(String[] args) {
              // TODO Auto-generated method stub

              Scanner cin = new Scanner(System.in);
              int n;

              while (cin.hasNext()){
                     n = cin.nextInt();
                     int[][] a = new int[n][n];
                     for (int i = 0; i < n; i++){
                            for (int j = 0; j < n; j++){
                                   a[i][j] = cin.nextInt();                                  
                            }
                     }
                     System.out.println(maxTotal(a, n));
              }
       }
}