DP专题4 UVAOJ 108 Maximum Sum

传送门：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44

Maximum Sum

Time Limit:1000MS Memory Limit:16384KB 64bit IO Format:%I64d & %I64u

Background

A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.

The Problem

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. 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. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

is in the lower-left-hand corner:

and has the sum of 15.

Input and Output

The input consists of an array of integers. The input begins with a single positive integerN on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on 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].

The output is the sum of the maximal sub-rectangle.

Sample Input

40 -2 -7  0 9  2 -6  2-4  1 -4  1 -18  0 -2

Sample Output

15

问题描述：

给定一个矩阵数组，求出任意一个子矩阵，使其总数之和最大。

算法分析：

首先想到的应该是暴力求解法，求出每一种可能的矩阵，然后计算其内数字之和，比较。但是，这种算法明显是一种代价太大的算法。这里，影响想到一种压缩的思路，联系到DP2中的数组，对于一个确定的最优解，假设是M * N的数组矩阵，我们可以将他压缩成一个1 * N的矩阵，即把每一竖条的数全部相加。如果想到了这个，应该就能得到这题的思路了。我们可以把整个矩阵分为每连续1行、2行、3行……一直到n行压缩为一个1*N的数组，然后运用DP2中的方法求出最大和即可。有了这个思路，整个算法的设计就是比较轻松的了，需要注意的是细节上的处理。虽然这个算法是O（n^3）的，但是还是过了，确实还没想到比这更好的方法了，以后琢磨出来再更新~

代码如下：

/*Memory: 160 KB   Time: 31 MS  Language: C   Result: Accepted   This source is shared by hust_lcl*/#include <stdio.h>#include <stdlib.h>int n ;int input[110][110];int max = -99999999;int dp[110];int temp[110];void DP(){    int i ;    temp[1] = dp[1];    for(i = 2 ; i <= n ; i++)    {        if(temp[i-1]>0)          temp[i] = temp[i-1] + dp[i];        else          temp[i] = dp[i];    }    for(i = 1 ; i <= n ; i++)      if(temp[i] > max)        max = temp[i];}int main(){    int i , j , k ;    scanf("%d",&n);    for(i = 1 ; i <= n ; i ++)      for(j = 1 ; j <=n ; j ++)        scanf("%d",&input[i][j]);    for(i = 1 ; i <= n ; i ++)    {        memset(dp,0,sizeof(dp));//每次DP前要清零        for(j = i ; j <= n ; j ++)        {            for(k = 1 ; k <= n ; k ++)              dp[k] += input[j][k];            DP();        }    }    printf("%d\n",max);    return 0;}