Cho ma trận NxN tìm ma trận con của MxM trong đó M <=N và M> =1 sao cho phép cộng tất cả các phần tử của ma trận MxM là cực đại. Đầu vào của ma trận NxN có thể chứa các giá trị nguyên dương và âm 0.
Ví dụ
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 Bài toán trên có thể được giải bằng một giải pháp đơn giản, trong đó chúng ta có thể lấy toàn bộ ma trận NxN, sau đó tìm tất cả các ma trận MxM có thể có và tìm tổng của chúng, sau đó in ra một ma trận MxM với tổng lớn nhất. Cách tiếp cận này dễ dàng nhưng đòi hỏi độ phức tạp về thời gian là O (N ^ 2.M ^ 2), vì vậy chúng tôi cố gắng tìm ra cách ít tốn thời gian hơn.
Thuật toán
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 \n
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 Ví dụ
#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;
} Đầu ra
nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau
4 4 5 5