描述
计算矩阵中，最大和的子矩阵，并输出最大的和
测试用例
用例一：
$$\begin{equation} \begin{bmatrix*}[c] -3 & -5 & -1 & 5 \newline 2 & -4 & -2 & 4 \newline -1 & 3 & -1 & 3 \end{bmatrix*} \end{equation}$$
用例二：
$$\begin{equation} \begin{bmatrix*}[c] -3 & -5 & -1 & 5 \newline 9 & -4 & -2 & 4 \newline -1 & 3 & -1 & 3 \end{bmatrix*} \end{equation}$$
用例三：
$$\begin{equation} \begin{bmatrix*}[c] -3 & -5 & -1 & 5 \newline 7 & -4 & -2 & 4 \newline -1 & 3 & -1 & 3 \end{bmatrix*} \end{equation}$$
用例四：
$$\begin{equation} \begin{bmatrix*}[c] -3 & -5 & -1 & 5 \newline 9 & -4 & -2 & 4 \newline -1 & -2 & -1 & -3 \end{bmatrix*} \end{equation}$$
用例五：
$$\begin{equation} \begin{bmatrix*}[c] -3 & -5 & -1 & 5 \newline 9 & -4 & -3 & 4 \newline -1 & -2 & -1 & -3 \end{bmatrix*} \end{equation}$$
用例六：
$$\begin{equation} \begin{bmatrix*}[c] -3 & -5 & -1 & 5 \newline 9 & 1 & -7 & 4 \newline -1 & -2 & -1 & -3 \end{bmatrix*} \end{equation}$$
用例七：
$$\begin{equation} \begin{bmatrix*}[c] -3 & 5 & -1 & -5 \newline 9 & 4 & -7 & -4 \newline -1 & 3 & -1 & -3 \end{bmatrix*} \end{equation}$$
用例八：
$$\begin{equation} \begin{bmatrix*}[c] -3 & 2 & -1 & 2 \newline 5 & 4 & -2 & 0 \newline -1 & 3 & -1 & 2 \end{bmatrix*} \end{equation}$$
用例九：
$$\begin{equation} \begin{bmatrix*}[c] -3 & 5 & -1 & -5 \newline 2 & 4 & -2 & -4 \newline -1 & 3 & -1 & -3 \end{bmatrix*} \end{equation}$$
用例十：
$$\begin{equation} \begin{bmatrix*}[c] -3 & 3 & -1 & -5 \newline 9 & -4 & -7 & -4 \newline -1 & 3 & -1 & -3 \end{bmatrix*} \end{equation}$$
测试用例十一：
$$\begin{equation} \begin{bmatrix*}[c] 1 & 2 & 3 & 4 \newline 5 & 6 & 7 & 8 \newline 9 & 10 & 11 & 12 \end{bmatrix*} \end{equation}$$
测试用例十二：
$$\begin{equation} \begin{bmatrix*}[c] -1 & -2 & -3 & -4 \newline -5 & -6 & -7 & -8 \newline -9 & -10 & -11 & -12 \end{bmatrix*} \end{equation}$$
测试用例十三：
$$\begin{equation} \begin{bmatrix*}[c] -12 & -11 & -10 & -9 \newline -8 & -7 & -6 & -5 \newline -4 & -3 & -2 & -1 \end{bmatrix*} \end{equation}$$
方法一：暴力算法
void testMatMaxSum() {
/*int arr[][4] = {
{-3, -5, -1, 5},
{2, -4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, -4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{7, -4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, -4, -2, 4},
{-1, -2, -1, -3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, 1, -3, 4},
{-1, -2, -1, -3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, 1, -7, 4},
{-1, -2, -1, -3}
};*/
/*int arr[][4] = {
{-3, 5, -1, -5},
{9, 4, -7, -4},
{-1, 3, -1, -3}
};*/
/*int arr[][4] = {
{-3, 2, -1, 2},
{5, 4, -2, 0},
{-1, 3, -1, 2}
};*/
/*int arr[][4] = {
{-3, 5, -1, 5},
{2, 4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, 3, -1, -5},
{9, -4, -7, -4},
{-1, 3, -1, -3}
};*/
/*int arr[3][4]{ 0 };
int n = 1;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 4; ++j) {
arr[i][j] = n++;
}
}*/
int arr[3][4]{0};
int n = -12;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 4; ++j) {
arr[i][j] = n++;
}
}
int dp[4][5]{ 0 };
for (int i = 1; i < 4; ++i)
{
for (int j = 1; j < 5; ++j)
{
dp[i][j] = arr[i - 1][j - 1];
}
}
for (int i = 1; i < 4; ++i)
{
for (int j = 1; j < 5; ++j)
{
dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
int start_x = 1, start_y = 1, end_x = 1, end_y = 1;
int max_sum = dp[start_x][start_y];
for (int x = 0; x < 3; x++)
{
for (int y = 0; y < 4; y++)
{
for (int i = 1; i < 4-x; i++)
{
for (int j = 1; j < 5-y; j++)
{
int b = i + x;
int r = j + y;
int cur_sum = dp[b][r] - dp[b][j - 1] - dp[i - 1][r] + dp[i - 1][j - 1];
if (max_sum < cur_sum)
{
max_sum = cur_sum;
start_x = i;
start_y = j;
end_x = b;
end_y = r;
}
}
}
}
}
cout << "max: " << max_sum << endl;
cout << "左上：[" << (start_x - 1) << ", " << (start_y - 1) << "] 右下：[" << (end_x - 1) << ", " << (end_y - 1) << "]" << endl;
}
方法二：模拟人的思维方式
此方法要考虑的情况较多
void testMatMaxSum() {
/*int arr[][4] = {
{-3, -5, -1, 5},
{2, -4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, -4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{7, -4, -2, 4},
{-1, 3, -1, 3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, -4, -2, 4},
{-1, -2, -1, -3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, 1, -3, 4},
{-1, -2, -1, -3}
};*/
/*int arr[][4] = {
{-3, -5, -1, 5},
{9, 1, -7, 4},
{-1, -2, -1, -3}
};*/
/*int arr[][4] = {
{-3, 5, -1, -5},
{9, 4, -7, -4},
{-1, 3, -1, -3}
};*/
/*int arr[][4] = {
{-3, 2, -1, 2},
{5, 4, -2, 0},
{-1, 3, -1, 2}
};*/
/*int arr[][4] = {
{-3, 5, -1, 5},
{2, 4, -2, 4},
{-1, 3, -1, 3}
};*/
int arr[][4] = {
{-3, 3, -1, -5},
{9, -4, -7, -4},
{-1, 3, -1, -3}
};
/*int arr[3][4]{ 0 };
int n = 1;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 4; ++j) {
arr[i][j] = n++;
}
}*/
/*int arr[3][4]{0};
int n = -12;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 4; ++j) {
arr[i][j] = n++;
}
}*/
int dp[4][5]{ 0 };
for (int i = 1; i < 4; ++i)
{
for (int j = 1; j < 5; ++j)
{
dp[i][j] = arr[i - 1][j - 1];
}
}
for (int i = 1; i < 4; ++i)
{
for (int j = 1; j < 5; ++j)
{
dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
int dp_max = arr[0][0], real_dp_max = dp_max;
int t = 1, l = 1, b = 1, r = 1;
for (int i = 1; i < 4; ++i)
{
int cur_t = 1, cur_l = 1, cur_b = 1, cur_r = 1;
for (int j = 1; j < 5; ++j)
{
// 根据矩阵元素的和的 dp 移动矩阵临时的左上角坐标和右下角坐标
if (dp_max < dp[i][j])
{
dp_max = dp[i][j];
cur_b = i;
cur_r = j;
}
if (cur_t != 1 || cur_l != 1)
{
int cur_real_dp_max = dp[i][j] - dp[i][cur_l - 1] - dp[cur_t - 1][j] + dp[cur_t - 1][cur_l - 1];
if (dp_max < cur_real_dp_max) {
dp_max = cur_real_dp_max;
cur_b = i;
cur_r = j;
}
}
if (dp_max < arr[i - 1][j - 1])
{
dp_max = arr[i - 1][j - 1];
cur_t = i;
cur_l = j;
cur_b = i;
cur_r = j;
}
// 判断是否需要改变最终矩阵的左上角和右下角坐标
// 如果矩阵的左上角坐标发生过变化，则需要与真实的矩阵最大和进行比较
if ((t != 1 || l != 1) && dp_max > real_dp_max)
{
int max_t = cur_t > t ? cur_t : t;
int max_l = cur_l > l ? cur_l : l;
// 分别计算 (t,l)-(max_t,max_l) 矩阵的和
// (cur_t,cur_l)-(max_t,max_l) 矩阵的和
// 只有当后者大于前者时才需更新矩阵的左上角坐标
int max_sum = dp[max_t][max_l] - dp[max_t][l - 1] - dp[t - 1][max_l] + dp[t - 1][l - 1];
int new_sum = dp[max_t][max_l] - dp[max_t][cur_l - 1] - dp[cur_t - 1][max_l] + dp[cur_t - 1][cur_l - 1];
if (max_sum < new_sum)
{
max_sum = new_sum;
t = cur_t;
l = cur_l;
}
if (real_dp_max < max_sum)
{
b = max_t;
r = max_l;
real_dp_max = max_sum;
}
}
if (i >= t && j >= l)
{
int cur_real_dp_max = dp[i][j] - dp[i][l - 1] - dp[t - 1][j] + dp[t - 1][l - 1];
if (real_dp_max < cur_real_dp_max)
{
b = i;
r = j;
real_dp_max = cur_real_dp_max;
}
}
if (real_dp_max < dp_max)
{
real_dp_max = dp_max;
t = cur_t;
l = cur_l;
b = cur_b;
r = cur_r;
}
}
}
cout << "max: " << real_dp_max << endl;
cout << "左上：[" << (t - 1) << ", " << (l - 1) << "] 右下：[" << (b - 1) << ", " << (r - 1) << "]" << endl;
}