資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究在 C 程式中列印給定大小的最大和方陣子矩陣。
給定 NxN 的矩陣，查詢 MxM 的子矩陣，其中 M<=N 和 M>=1，使矩陣 MxM 中所有元素的總和最大。矩陣 NxN 的輸入可以包含零、正和負整數。
例項
Input:
{{1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5} }
Output:
4 4
5 5上述問題可以透過一個簡單的解決方案來解決，其中我們可以採用整個矩陣 NxN，然後找出所有可能的矩陣 MxM 並求它們的和，最後打印出具有最大和的矩陣 MxM。這種方法簡單，但需要 O(N^2.M^2) 的時間複雜度，因此我們嘗試找出一種耗時較少的方法。
演算法
Start Step 1 -> Declare Function void matrix(int arr[][size], int k) IF k>size Return Declare int array[size][size] Loop For int j=0 and j<size and j++ Set sum=0 Loop for int i=0 and i<k and i++ Set sum=sum + arr[i][j] End Set array[0][j]=sum Loop For int i=1 and i<size-k+1 and i++ Set sum=sum+(arr[i+k-1]][j]-arr[i-1][j] Set arrayi][j]=sum End Set int maxsum = INT_MIN and *pos = NULL Loop For int i=0 and i<size-k+1 and i++) Set int sum = 0 Loop For int j = 0 and j<k and j++ Set sum += array[i][j] End If sum > maxsum Set maxsum = sum Set pos = &(arr[i][0]) End Loop For int j=1 and j<size-k+1 and j++ Set sum += (array[i][j+k-1] - array[i][j-1]) IF sum > maxsum Set maxsum = sum Set pos = &(arr[i][j]) End End End Loop For int i=0 and i<k and i++ Loop For int j=0 and j<k and j++ Print *(pos + i*size + j) End Print
End Step 2 -> In main() Declare int array[size][size] = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}, {4, 4, 4, 4, 4}, {5, 5, 5, 5, 5}} Declare int k = 2 Call matrix(array, k) Stop
例項
#include <bits/stdc++.h>
using namespace std;
#define size 5
void matrix(int arr[][size], int k){
if (k > size) return;
int array[size][size];
for (int j=0; j<size; j++){
int sum = 0;
for (int i=0; i<k; i++)
sum += arr[i][j];
array[0][j] = sum;
for (int i=1; i<size-k+1; i++){
sum += (arr[i+k-1][j] - arr[i-1][j]);
array[i][j] = sum;
}
}
int maxsum = INT_MIN, *pos = NULL;
for (int i=0; i<size-k+1; i++){
int sum = 0;
for (int j = 0; j<k; j++)
sum += array[i][j];
if (sum > maxsum){
maxsum = sum;
pos = &(arr[i][0]);
}
for (int j=1; j<size-k+1; j++){
sum += (array[i][j+k-1] - array[i][j-1]);
if (sum > maxsum){
maxsum = sum;
pos = &(arr[i][j]);
}
}
}
for (int i=0; i<k; i++){
for (int j=0; j<k; j++)
cout << *(pos + i*size + j) << " ";
cout << endl;
}
}
int main(){
int array[size][size] = {
{1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5},
};
int k = 2;
matrix(array, k);
return 0;
}輸出
如果我們執行上述程式，它將生成以下輸出
4 4 5 5
更新日期：2019 年 8 月 22 日
532 次瀏覽
廣告