資料結構
網路
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 次檢視
