在C语言中:输入是一个N*N的矩阵。输入的第一行给出N (0<N<=100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]。注意,样例输入中,的确有一个空行。 输出描述: 输出最大子矩阵的大小
时间: 2024-02-12 08:06:23 浏览: 116
以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
int main()
{
int n;
scanf("%d", &n);
int a[110][110], dp[110][110], sum[110][110];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
dp[i][j] = a[i][j];
}
}
int ans = dp[1][1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] + sum[i][j] - sum[i-1][j] - sum[i][j-1] + a[i][j]);
ans = max(ans, dp[i][j]);
}
}
printf("%d\n", ans);
return 0;
}
```
这里使用了两个二维数组,dp[i][j]表示以(i,j)为右下角的最大子矩阵的大小,sum[i][j]表示以(i,j)为右下角的子矩阵的大小。在读入矩阵时,同时计算出sum数组的值。在动态规划时,使用sum数组来计算以(i,j)为右下角的子矩阵的大小。最后遍历dp数组,找出其中的最大值即为所求。
阅读全文
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)