The Odyssey of DP —— 最大子矩阵

发表于 | 分类于 | 浏览次数
字数统计: 1,022 字 | 阅读时长 ≈ 5 分钟

1. 最大连续子序列和

给定一个数字序列 $A_{1}, A_{2}, \cdots, A_{n}$，求i，j（1$\le i \le j \le n$），使得$A_{i} + \cdots + A_{j} $最大，输出这个最大和。

样例：

-2 11 -4 13 -5 -2

显然 11+(-4)+13=20为和最大的选取情况，因此最大和为20

使用动态规划，复杂度为O(n)的做法：设置dp[i]表示以A[i]作为末尾的连续序列的最大和，如此一来，要求的最大和其实就算dp[0]，dp[1]，$\cdots$，dp[n-1]中的最大值，下面想办法求解dp数组。

因为dp[i]要求必须是以A[i]作为末尾的连续序列的最大和，那么只有两种情况：

  • 这个最大和的连续序列只有一个元素，即A[i];
  • 这个最大和的连续序列有多个元素，即从前面某处A[p]开始（p<i），一直到A[i]结尾。

对于第一种情况，最大和就是A[i]本身。对于第二种情况，最大和是dp[i-1]+A[i]。于是得到状态转移方程

依此写出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10010;
int A[maxn], dp[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i< n; i++)
    	scanf("%d", &A[i]);
    dp[0] = A[0];
    for(int i = 1; i < n; i++)
    	dp[i] = max(A[i], dp[i-1] + A[i]);
    int k = 0;
    for(int i = 1; i < n; i++)
    {
        if(dp[i] > dp[k])
            k = i;
    }
    printf("%d\n", dp[k]);
    return 0;
}

不需要记录每个index的连续序列的最大和时可以写成以下简洁的形式：

1
2
3
4
5
6
7
8
9
10
11
12
int maxSubArray(int* a, int n)//一维数组的最大连续子序列
{
	if (!a || n <= 0)
		return 0;
	int themax = a[0], curmax = a[0];
	for (int i = 1; i < n; i++)
	{
		curmax = max(a[i], curmax + a[i]);
		themax = max(themax, curmax);
	}
	return themax;
}

2. 最大子矩阵和

已知矩阵的大小定义为矩阵中所有元素的和。
第一行输入一个方阵的行数n，之后的n行输入方阵的每个元素，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
n
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。

直觉上来看，这个问题就是上述最大连续子序列和拓展到二维的情况。那么关键在于如何将两者联系起来。首先我们知道一定存在0$\le i \le j \le n-1$，最优解就在第i行和第j行之间，剩下的就是去确定两个列，我们可以通过遍历所有i, j的情况，针对一对确定的i, j，我们将每一列的[i, j]行之间的数各自相加。得到一个一维数组，$a[i][0] + $\cdots$ + a[j][0], $\cdots$, a[i][n-1] + $\cdots$ + a[j][n-1]$，而后对这个一维的和数组求最大连续子序列和。最后求出上述每个i, j的最大连续子序列和的最大值即为最大子矩阵和。得到一个$O(n^3)$的算法。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int MAXV = 110;
int matrix[MAXV][MAXV];
int tmp[MAXV]; //用于保存\[i, j\]行之间的数各自相加的一维数组
void MaxSubMatrix()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &matrix[i][j]);
	int tmpsum, themax = -1000000000;
	for (int i = 0; i < n; i++)
	{
		fill(tmp, tmp + n, 0);//每次移动i的时候tmp数组清零
		for (int j = i; j < n; j++)//遍历所有i, j的情况
		{
			for (int k = 0; k < n; k++)
			{
				tmp[k] += matrix[j][k];//重复利用tmp，因为对于i, j的遍历是先固定i，递增j，所以当j从p变为p+1时，可以利用$tmp_p$加上第p+1行的元素即可
			}
			tmpsum = maxSubArray(tmp, n); //上述的最大连续序列和
			themax = max(themax, tmpsum);
		}
	}
	printf("%d\n", themax);
}