การพิมพ์เมทริกซ์ย่อยสี่เหลี่ยมจัตุรัสที่มีผลรวมมากที่สุดขนาดกำหนดในโปรแกรม C

ได้รับเมทริกซ์ NxN หาเมทริกซ์ย่อย MxM โดย M<=N และ M>=1 ที่ผลรวมองค์ประกอบมากที่สุด อินพุทอาจมีค่าศูนย์ บวก และลบ

ตัวอย่าง

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

วิธีง่ายคือหาเมทริกซ์ย่อย 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; j maxsum
      Set maxsum = sum
      Set pos = &(arr[i][0])
    End
    Loop For int j=1; j maxsum
        Set maxsum = sum
        Set pos = &(arr[i][j])
      End
    End
  End
  Loop For int i=0; i 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

ตัวอย่างโค้ด C++

#include 
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 maxsum){
            maxsum = sum;
            pos = &(arr[i][0]);
        }
        for (int j=1; j maxsum){
                maxsum = sum;
                pos = &(arr[i][j]);
            }
        }
    }
    for (int i=0; i
ผลลัพธ์
การรันโปรแกรมจะได้ผลลัพธ์ดังนี้:
4 4
5 5