最小矩阵和

胖胖程序相关 2010/09/03 2 条留言 735 views

很久很久以前的代码，在某个角落找到，贴了上来，
在杭电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));
              }
       }
}

本文地址：最小矩阵和文章出处：PHP源码阅读，PHP设计模式，PHP学习笔记，项目管理-胖胖的空间

转载请以链接形式注明原始出处和作者，谢绝不尊重版权者抄袭！

标签：ACM, DP, dynamic programming

2 条留言我要留言

先顶, 后看, 必须的..

- -, 看不懂..