美文网首页LeetCode程序员Leetcode
Leetcode. 子矩阵的最大累加和问题

Leetcode. 子矩阵的最大累加和问题

作者: 周肃 | 来源:发表于2017-05-21 09:44 被阅读124次

    问题描述

    给定一个矩阵Matrix, 其中的值由正, 有负, 有0, 返回子矩阵的最大累加和.

    例如: 给定矩阵
    | -90 | 48 |78 |
    | 64 | -40 | 64 |
    | -81 | -7 | 66 |

    累加和最大的子矩阵为
    | 48 | 78 |
    | -40| 64 |
    | -7 | 66 |

    问题分析

    不同于数组, 矩阵需要在两个维度上进行移动, 所以逐个子矩阵尝试的方法, 复杂度很高.
    一个思路是, 将矩阵的最大累加和转换为数组的最大累加和.
    以矩阵
    | -2 | 3 | -5 | 7 |
    | 1 | 4 | -1 | -3 |
    为例
    1 第一行作为一个数组, 求它的最大子数组累加和 7
    2 第二行作为一个数组, 求它的最大子数组累加和 5
    3 将矩阵的两行数字对应相加, 得到数组 | -1 | 7 | -6 | 4 |, 求这个数组的最大累加和为7
    4 求所得累加和中最大的值, 即为7.
    也就是说, 在矩阵中, 限定某k行, 在必须含有k行元素的情况下, 可以通过将每一列的k个元素累加生成一个累加数组, 然后求出这个数组的最大累加和max, 就是必须含有k行元素的子矩阵中的最大累加和.

    实现

    class Solution
    {
    public:
        int maxSumMatrix(std::vector<std::vector<int>>& matrix)
        {   
            if (matrix.size() == 0 || matrix[0].size() == 0)
            {   
                return 0;
            }   
            int rowCount = matrix[0].size();
            int max = INT_MIN;
            std::vector<int> arr;
            for (int startLine = 0; startLine < matrix.size(); ++startLine)
            {   
                arr.assign(rowCount, 0); 
                for (int lineNum = startLine; lineNum < matrix.size(); ++lineNum)
                {   
                    for (int rowNum = 0; rowNum < rowCount; ++rowNum)
                    {   
                        arr[rowNum] += matrix[lineNum][rowNum];
                    }   
                    int tempMax= maxSumOfArray(arr);
                    max = std::max(tempMax, max);
                }   
            }   
            return max;
        }   
    private:
        int maxSumOfArray(const std::vector<int>& arr)
        {   
            int max = INT_MIN;
            int cur = 0;
            for (auto each : arr)
            {   
                cur = cur + each >= 0 ? cur + each : 0;
                max = cur > max ? cur : max;
            }   
            return max;
        }   
    };
    

    相关文章

      网友评论

        本文标题:Leetcode. 子矩阵的最大累加和问题

        本文链接:https://www.haomeiwen.com/subject/qvsmxxtx.html