数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定二维数组中最小和子矩阵（C++）
给定一个由整数元素组成的二维数组，形成矩阵。任务是计算从形成的矩阵中提取子矩阵的最小和的次数。
让我们看看这个的不同输入输出场景 -
输入 -int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
输出 -给定二维数组中最小和子矩阵是：-9
解释 -给定一个大小为 4x4 的二维数组，即 4 行 4 列。现在，我们将从给定矩阵中找出子矩阵，使得最小子矩阵为 -9。
输入 -int matrix[row][column] = { {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}
输出 -给定二维数组中最小和子矩阵是：-3
解释 -给定一个大小为 3x3 的二维数组，即 3 行 3 列。现在，我们将从给定矩阵中找出子矩阵，使得最小子矩阵为 -3，这是通过给定矩阵中的第二行实现的，子矩阵的大小为 1x3，即 1 行 3 列。
下面程序中使用的的方法如下 -
输入一个整数二维数组并将数据传递给函数 Minimum_Matrix(matrix) 以进行进一步处理。
在函数 Minimum_Matrix(matrix) 内部
声明临时变量为 int result = INT_MAX, int arr[row], int total, int first 和 int end。
从 int 到 temp 开始循环 FOR，直到 temp 小于 column。在循环内将数组元素设置为 0。从 int 到 temp_2 开始另一个循环 FOR，直到 temp_2 小于 column。在循环内，从 int i 到 0 开始另一个循环，直到 i 小于 row 并将 arr[i] 设置为 ar[i] + matrix[i][temo_2]。
将 total 设置为对函数 Algo_Kad(arr, &first, &end, row) 的调用
检查 IF total 小于 result，然后将 result 设置为 total
打印 result 作为最终输出。
在函数 int Algo_Kad(int* arr, int* first, int* end, int max_size) 内部
声明临时变量为 int total 为 0，int result 为 INT_MAX，int temp 为 0 和 *end = -1
从 i 到 0 开始循环 FOR，直到 i 小于 max_size。在循环内，将 total 设置为 total + arr[i]。
检查 IF total 大于 0，然后将 total 设置为 0 并将 temp 设置为 i + 1。
否则 IF，检查 total 小于 result，然后将 result 设置为 total，*first 设置为 temp 并将 *end 设置为 i
现在，检查 IF *end 不等于 -1，然后返回 result。
将 result 设置为 arr[0]，*first 设置为 0 并将 *end 设置为 0
从 i 到 1 开始循环 FOR，直到 i 小于 max_size。在循环内，检查 IF arr[i] 小于 result，然后将 result 设置为 arr[i]，*first 设置为 i 并将 *end 设置为 i
返回 result。
示例
#include <bits/stdc++.h>
using namespace std;
#define row 4
#define column 4
int Algo_Kad(int* arr, int* first, int* end, int max_size)
{
int total = 0;
int result = INT_MAX;
int temp = 0;
*end = -1;
for(int i = 0; i < max_size; ++i)
{
total = total + arr[i];
if(total > 0)
{
total = 0;
temp = i + 1;
}
else if(total < result)
{
result = total;
*first = temp;
*end = i;
}
}
if(*end != -1)
{
return result;
}
result = arr[0];
*first = 0;
*end = 0;
for(int i = 1; i < max_size; i++)
{
if(arr[i] < result)
{
result = arr[i];
*first = i;
*end = i;
}
}
return result;
}
void Minimum_Matrix(int matrix[][column])
{
int result = INT_MAX;
int arr[row];
int total;
int first;
int end;
for(int temp = 0; temp < column; ++temp)
{
memset(arr, 0, sizeof(arr));
for(int temp_2 = temp; temp_2 < column; ++temp_2)
{
for(int i = 0; i < row; ++i)
{
arr[i] = arr[i] + matrix[i][temp_2];
}
total = Algo_Kad(arr, &first, &end, row);
if(total < result)
{
result = total;
}
}
}
cout<<"Minimum sum submatrix in a given 2D array is: "<<result;
}
int main()
{
int matrix[row][column] = {{2, 3, -1, 5},
{-2, 9, -1, 6},
{ 5, 6, 9, -9},
{ -6, 1, 1, 1} };
Minimum_Matrix(matrix);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出
Minimum sum submatrix in a given 2D array is: -9
492 次查看
