Maximum Subarray Problem

/* Example:
 * 41  17  47
 * 33 -16 -16
 * 26 -30  36
 * -3 -18 -19
 * Max submatrix sum: 138
 * Start (0, 2)
 * End   (0, 2)
 * 41  17  47
 * 33 -16 -16
 * 26 -30  36
 */
#include <iostream>
#include <iomanip>
#include <ctime>
#include <array>

template <typename ElemType, size_t Row, size_t Column>
using Matrix = std::array<std::array<ElemType, Column>, Row>;

template <typename Matrix>
using StorageType = typename Matrix::value_type::value_type;

template <typename Matrix>
auto getSubmatrixSum(const Matrix& matrix, size_t startX, size_t endX, size_t startY, size_t endY) {
    StorageType<Matrix> sum{ 0 };
    for (size_t x = startX; x <= endX; ++x) {
        for (size_t y = startY; y <= endY; ++y) {
            sum += matrix[x][y];
        }
    }
    return sum;
}

template <typename Matrix>
void generateRandomMatrix(Matrix& matrix) {
    // Инициализируем генератор псевдослучайных чисел
    std::srand(unsigned(std::time(0)));

    for (size_t x = 0U; x < matrix.size(); x++) {
        for (size_t y = 0U; y < matrix[x].size(); y++) {
            matrix[x][y] = std::rand() % 100 - 50;
        }
    }
}

int main() {
    constexpr size_t rowCount = 4U;
    constexpr size_t colCount = 3U;

    using ElemType = float;

    Matrix<ElemType, rowCount, colCount> matrix;
    generateRandomMatrix(matrix);

    // Выводим матрицу
    for (size_t x = 0U; x < rowCount; ++x) {
        for (size_t y = 0U; y < colCount; ++y) {
            std::cout << std::setw(3) << matrix[x][y] << " ";
        }
        std::cout << std::endl;
    }

    // Храним данные о максимальной сумме
    struct {
        ElemType sum = std::numeric_limits<ElemType>::min();
        size_t startX;
        size_t startY;
        size_t endX;
        size_t endY;
    } submatrix;

    // Перемещаем 'начальную' клетку
    for (size_t startX = 0U; startX < rowCount; ++startX) {
        for (size_t startY = 0U; startY < colCount; ++startY) {

            // Перемещаем конечную клетку
            for (size_t endX = rowCount - 1U;; --endX) {
                for (size_t endY = colCount - 1U;; endY--) {
                    // Считаем сумму текущей подматрицы
                    ElemType sum = getSubmatrixSum(matrix, startX, endX, startY, endY);

                    // Если сумма элементов текущей подматрицы больше, то сохраняем
                    if (sum > submatrix.sum) {
                        submatrix.sum = sum;
                        submatrix.startX = startX;
                        submatrix.startY = startY;
                        submatrix.endX = endX;
                        submatrix.endY = endY;
                    }
                    if (endY == startY) break;
                }
                if (endX == startX) break;
            }
        }
    }

    std::cout << "Max submatrix sum: " << submatrix.sum << std::endl;
    std::cout << "Start (" << submatrix.startX << ", " << submatrix.endX << ")" << std::endl;
    std::cout << "End   (" << submatrix.startY << ", " << submatrix.endY << ")" << std::endl;

    // Выводим подматрицу
    for (size_t x = submatrix.startX; x <= submatrix.endX; ++x) {
        for (size_t y = submatrix.startY; y <= submatrix.endY; ++y) {
            std::cout << std::setw(3) << matrix[x][y] << " ";
        }
        std::cout << std::endl;
    }

    system("pause");
}