ให้เมทริกซ์ของ 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 \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
