题解 | #最大子矩阵#

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class solution
{
public:
    int getResult(vector<vector<int>> &matrix)
    {
        // 求前缀和
        for (int i = 1; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {
                matrix[i][j] += matrix[i - 1][j];
            }
        }
        
        int ret = INT_MIN;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = i; j < matrix[0].size(); j++)
            {
                vector<int> tmp(matrix[0].size());
                for (int k = 0; k < tmp.size(); k++)
                {
                    if (i == 0)
                    {
                        tmp[k] = matrix[j][k];
                    }
                    else
                    {
                        tmp[k] = matrix[j][k] - matrix[i - 1][k];
                    }
                }
                
                ret = max(ret, getSubArrayMax(tmp));
            }
        }
        
        return ret;
    }
    
    // 求连续子数组最大和
    int getSubArrayMax(vector<int> &nums)
    {
        int ret = nums[0];
        int dp = nums[0];
        
        for (int i = 1; i < nums.size(); i++)
        {
            dp = max(dp + nums[i], nums[i]);
            ret = max(ret, dp);
        }
        
        return ret;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    while (cin >> n)
    {
        vector<vector<int>> matrix(n, vector<int>(n));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> matrix[i][j];
            }
            cin.get();
        }
        cout << mSolution.getResult(matrix);
    }
    
    return 0;
}