NxN의 행렬이 주어지면 MxM의 모든 요소의 합이 최대가 되도록 M<=N 및 M>=1인 MxM의 하위 행렬을 찾습니다. 행렬 NxN의 입력은 0, 양수 및 음수 정수 값을 포함할 수 있습니다.
예시
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 \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 예시
#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