In ma trận con vuông có tổng lớn nhất kích thước cho trước trong C

Cho ma trận NxN, tìm ma trận con MxM (M <= N) có tổng các phần tử lớn nhất. Ma trận có thể chứa số âm, 0, dương.

Ví dụ

Input: 5x5 matrix với các hàng: {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}, k=2
Output:
4 4
5 5

Giải pháp tối ưu dùng mảng tiền tính tổng cột (prefix sum) để giảm độ phức tạp từ O(N²M²) xuống O(N²).

Thuật toán

BẮT ĐẦU
HÀM matrix(int arr[][size], int k)
    NẾU k > size TRẢ VỀ
    TẠO mảng array[size][size] lưu tổng cột
    VỚI j=0 ĐẾN size-1
        TÍNH TỔNG k PHẦN TỬ ĐẦU CỘT j -> array[0][j]
        VỚI i=1 ĐẾN size-k: CẬP NHẬT TRƯỢT (sliding window)
    maxsum = INT_MIN, pos = NULL
    VỚI i=0 ĐẾN size-k
        TÍNH TỔNG k CỘT ĐẦU -> sum
        CẬP NHẬT maxsum, pos
        VỚI j=1 ĐẾN size-k: TRƯỢT CỘT, CẬP NHẬT sum, maxsum, pos
    IN MA TRẬN KxK TẠI VỊ TRÍ pos
KẾT THÚC

Chương trình C++ 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;
}

Kết quả

4 4
5 5