Poj 1050 To the Max (最大子矩阵 DP)-蒲公英云

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

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

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

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

思路：先来看最大子段和怎么求，这部分的节选自：最大子段和各种算法讨论_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来临时存取，因此时间复杂度空间复杂度都是线性的。