蓝桥杯历届试题-最大子阵 （C++代码）

解题思路:
即便是使用了dp，复杂度依然是O(nm²)，在一些优化技巧的帮助下，勉强可以承受最大为500的数据规模的打击，时间在700ms上下

注意事项:

优化：

1. 不要用算法模板里的max，直接用三目运算符或者if语句

2. 矩阵不要用cin输入了，cin比scanf耗时不少，在这种严苛的情形下比较重要

坑：

拒绝值为负的子阵，否则会可能会削减最大子阵的值，导致答案错误！

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <list>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#define N 500

using namespace std;

int dp[N + 2][N + 2];
int A[N + 2][N + 2];

int solve(int n, int m)
{
	int ans = A[1][1];
	//初始化dp数组
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = dp[i][j - 1] + A[i][j];

	//计算最大子阵
	for (int first = 1; first <= m; first++)
	{
		for (int last = first; last <= m; last++)
		{
			int subMatrixSum = 0;
			for (int i = 1; i <= n; i++)
			{
				subMatrixSum += dp[i][last] - dp[i][first - 1];
				ans = ans > subMatrixSum ? ans : subMatrixSum;
				subMatrixSum = subMatrixSum > 0 ? subMatrixSum : 0;//重要，拒绝负子阵。否则有可能会削减最大子阵的值，导致错误结果
			}
		}
	}

	return ans;
}

int main()
{
	int m, n;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> A[i][j];
	cout << solve(n, m) << endl;
	return 0;
}