Poj 1050 To the Max (最大子矩阵 DP)

客官°小女子只卖身不卖艺 2022-09-17 13:22 170阅读 0赞

2015-4-27更新，百度空间即将关闭，把提到的文章整体复制到了最下面。

看了一篇博文很有启发：[最大全1子矩阵 - zhang20072844的专栏 - 博客频道 - CSDN.NET][1_ - zhang20072844_ - _ - CSDN.NET]

于是就找了一道没什么关系但是很基础的DP题。

题意：给出一个矩阵，求一个子矩阵使其内部元素之和最大。

思路：先来看最大子段和怎么求，这部分的节选自：[最大子段和 各种算法讨论\_Macrofuns™\_百度空间][_Macrofuns]

我们令一个数组f，f\[i\]表示前i个元素能组成的最大和。如果f\[i-1\]大于零，则不管a\[i\]的情况，f\[i-1\]都可以向正方向影响a\[i\]，因此可以将a\[i\]加在f\[i-1\]上。如果f\[i-1\]小于零，则不管a\[i\]再大，都会产生负影响，因此我们还不如直接令f\[i\]=a\[i\]。因此状态转移方程就在这里。我们只需在f中扫描一次，找到最大的值就是最大子段的和。

int LSS_DP (int a[])  //求最大子段和，动态规划，O(n)
    {
    	int f[101],n=a[0],max=-200000000; //f[i]表示第 i 个数能构成的最大和, max 表示当前所有中的最大和
    	f[1] = a[1];
    	for (int i=2;i<=n;i++)
    	{
    		if (f[i-1]>0)         //如果第 i 个数后面一个数能构成的最大子段和大于 0
    			f[i]=f[i-1]+a[i]; //大于就将第 i 个数加入其中
    		else
    			f[i]=a[i];        //否则第 i 个数自己组成一个最大子序列
    		if (f[i] > max)       //更新最大值
    			max=f[i];
    	}
    	return max;
    }

对于二维矩阵，我们可以把二维转换成一维的，把对应的列加起来，就可以把相邻的某几行转化为一维数组，用上面的方法求出最大和就可以了。这样，我们只要比较所有可能的相邻行的最大子数组结果就行了。

三维数组dp\[i\]\[j\]\[k\]，表示从第i行到第j行，所有第k列的元素之和，时间复杂度O(n^3)

#include <cstdio>
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=105;
    const int INF=0x3fffffff;
    
    int data[N][N],dp[N][N][N];
    int tmp[N],f[N];
    
    int main ()
    {
    	int n,i,j,k;
    	scanf("%d", &n);
    	for (i=0;i<n;i++)
    		for (j=0;j<n;j++)
    		{
    			scanf("%d",&data[i][j]);
    			dp[i][i][j]=data[i][j];
    		}
    	int ans=-INF;
    	for (i=0;i<n;i++)
    		for (j=0;j<i;j++)   //
    		{
    			for (k=0;k<n;k++)
    			{
    				dp[j][i][k]=dp[j][i-1][k]+data[i][k];
    				f[k]=tmp[k]=dp[j][i][k];
    			}
    			for (k=1;k<n;k++)
    				if (f[k-1]>0)
    					f[k]=f[k-1]+tmp[k];
    				else
    					f[k]=tmp[k];
    			for (k=0;k<n;k++)
    				ans=max(ans,f[k]);
    		}
    	printf("%d\n",ans);
    	return 0;
    }

文章备份：

## 最大子段和 各种算法讨论 ##

问题描述：

有n个数（以下都视为整数），每个数有正有负，现在要在n个数中选取相邻的一段，使其和最大，输出最大的和。

问题分析：

看到这个问题，它是属于带“最”字的问题，其实就是一个求最优解的问题。对于这种问题的朴素算法就是枚举出每种可能，然后在其中寻找一个最优的解，然后输出。因为输出仅要求这个子段的和，因此不必再记录关于解的组成的信息。

朴素算法是用i和j表示序列i到j的子段，然后判断这个子段的和是否是最大的，是就记录。然后用k求i到j之间的和，因此是O(n^3)的算法。

int LSS\_SlowEnumerate(int a\[\]) //最大子段和，枚举算法，O(n^3)  
\{  
int max = 0, n = a\[0\], sum;

for (int i = 1; i <= n; i++)  
\{  
for (int j = 1; j <= n; j++)  
\{  
sum = 0; //sum 为区间 \[i, j\] 之间的最大和  
for (int k = i; k <= j; k++)  
\{  
sum += a\[k\];  
\}

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

return max;  
\}

看了这个算法，我们不禁会想，有没有能更快的算法呢？毕竟O(n^3)的时间效率是很低的。答案肯定是有的，我们可以令一个数组sum，sum\[i\]代表了序列从1到i的和。如果要算i到j的和，只需将sum\[j\]减去sum\[i-1\]即可，这无疑可以去掉最里层的循环，从而直接调用和的信息，时间效率提高到O(n^2)。

int LSS\_Enumerate(int a\[\]) //最大子段和，枚举算法，O(n^2)  
\{  
int sum\[101\], i, n = a\[0\], max = -200000000, t; //sum\[i\] 表示 a\[i\] 的前 i 项和

sum\[0\] = 0;

for (i = 1; i <= n; i++)  
\{  
sum\[i\] = sum\[i - 1\] + a\[i\];  
\}

for (i = 0; i <= n - 1; i++) //枚举每个可能的子段  
\{  
for (int j = i + 1; j <= n; j++)  
\{  
t = sum\[j\] - sum\[i\];  
if (t > max)  
max = t;  
\}  
\}

return max;  
\}

上面两种算法都是朴素算法，枚举每个可能，从而找到最优的解。然而还有没有更优的解呢？答案依旧是肯定的。

我们不妨从小规模数据分析，当序列只有一个元素的时候，最大的和只有一个个可能，就是选取本身；当序列有两个元素的时候，只有三种可能，选取左边元素、选取右边元素、两个都选，这三个可能中选取一个最大的就是当前情况的最优解；对于多个元素的时候，最大的和也有三个情况，从左区间中产生、从右区间产生、左右区间各选取一段。因此不难看出，这个算法是基于分治思想的，每次二分序列，直到序列只有一个元素或者两个元素。当只有一个元素的时候就返回自身的值，有两个的时候返回3个中最大的，有多个元素的时候返回左、右、中间的最大值。因为是基于二分的思想，所以时间效率能达到O(nlgn)。

int LSS\_Recursion(int a\[\], int l, int r) //最大子段和，分治算法，O(nlgn)  
\{  
int m = (l + r) / 2, t = 0, L = 0, R = 0; //L为左区间能取到的最大，R为右区间能取到的最大

if (l == r) //边际条件：当区间元素只有一个的时候返回自身  
return a\[m\];

if (r - l == 1) //边际条件：当区间元素只有两个的时候返回左、右、左右相加三者中的最大值  
return Max(Max(a\[l\], a\[r\]), a\[l\] + a\[r\]);

int LMax = LSS\_Recursion(a, l, m); //递归左区间  
int RMax = LSS\_Recursion(a, m + 1, r); //递归右区间

for (int i = m; i >= 1; i--) //左边找一个最大的和  
\{  
t += a\[i\];  
if (t > L)  
L = t;  
\}

t = 0;

for (int i = m + 1; i <= r; i++) //右边找一个最大的和  
\{  
t += a\[i\];  
if (t > R)  
R = t;  
\}  
  
return Max(Max(LMax, RMax), L + R); //返回左区间的和、右区间的和、两者连起来的和中最大的  
\}

有了O(nlgn)的递归算法，那还能找到O(n)线性时间的算法么？——动态规划。我们令一个数组f，f\[i\]表示前i个元素能组成的最大和。如果f\[i-1\]大于零，则不管a\[i\]的情况，f\[i-1\]都可以向正方向影响a\[i\]，因此可以将a\[i\]加在f\[i-1\]上。如果f\[i-1\]小于零，则不管a\[i\]再大，都会产生负影响，因此我们还不如直接令f\[i\]=a\[i\]。因此状态转移方程就在这里。我们只需在f中扫描一次，找到最大的值就是最大子段的和。

int LSS\_DP(int a\[\]) //求最大子段和，动态规划，O(n)  
\{  
int f\[101\], n = a\[0\], max = -200000000; //f\[i\]表示第 i 个数能构成的最大和， max 表示当前所有中的最大和

f\[1\] = a\[1\];

for (int i = 2; i <= n; i++)  
\{  
if (f\[i - 1\] > 0) //如果第 i 个数后面一个数能构成的最大子段和大于 0  
\{  
f\[i\] = f\[i - 1\] + a\[i\]; //大于就将第 i 个数加入其中  
\}  
else  
f\[i\] = a\[i\]; //否则第 i 个数自己组成一个最大子序列

if (f\[i\] > max) //更新最大值  
max = f\[i\];  
\}

return max;  
\}

以上四个算法，从3个不同的思想解决了最大子段和问题，不管从时间效率还是代码量来说，动态规划都是最优的，仅需要一个辅助数组f来临时存取，因此时间复杂度空间复杂度都是线性的。

[1_ - zhang20072844_ - _ - CSDN.NET]: http://blog.csdn.net/zhang20072844/article/details/12925581
[_Macrofuns]: http://hi.baidu.com/macrofuns/item/21fc130ed6570adf72e67643