【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

这篇具有很好参考价值的文章主要介绍了【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

🚩 题目链接

  • 面试题 17.24. 最大子矩阵

⛲ 题目描述

给定一个正整数、负整数和 0 组成的 N × M 矩阵,编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2],其中 r1, c1 分别代表子矩阵左上角的行号和列号,r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵,返回任意一个均可。

注意:本题相对书上原题稍作改动

示例:

输入:
[
[-1,0],
[0,-1]
]
输出:[0,1,0,1]
解释:输入中标粗的元素即为输出所表示的矩阵

说明:

1 <= matrix.length, matrix[0].length <= 200

🌟 求解思路&实现代码&运行结果


⚡ 动态规划

🥦 求解思路
  1. 再学习这道题题目之前,大家可以先去看一下另一道最大子数组和的题解,再来学习这道题目就会非常容易。【LeetCode: 53. 最大子数组和 | 暴力递归=>记忆化搜索=>动态规划 | 分治法 】
  2. 我们先来简单理解一下这道题目的意思,这道题目区别于53.最大子数组和最大的不同在于,53题是一维的,但是这道题目是一个升级的版本,是二维的,但是核心的求解内思路是一样的。
  3. 既让说思路是一样的?那么我现在知道怎么求解一个一维数组的方法,但是并不知道二维数组怎么求解?这该怎么办呢?我们直接将二维数组转换为一维数组进性求解即可,怎么转换呢?就是挨个遍历从start开始,到end结束的行,按照列对其进行一个压缩即可。
  4. 然后我们找到最大子矩阵的和,如果当前的子矩阵的和是最大的,我们直接更新,并且抓取矩阵的坐标,最后直接返回即可。
  5. 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int r1=0,c1=0,r2=0,c2=0;
        int max=Integer.MIN_VALUE,cur=0;
        for(int i=0;i<m;i++){
            int[] temp=new int[n];
            for(int j=i;j<m;j++){
                int start=0;
                cur=0;
                for(int k=0;k<n;k++){
                    temp[k]+=matrix[j][k];
                    cur+=temp[k];
                    if(cur>max){
                        max=cur;
                        r1=i;
                        c1=start;
                        r2=j;
                        c2=k;
                    }
                    if(cur<0){
                        cur=0;
                        start=k+1;
                    }
                }
            }
        }
        return new int[]{r1,c1,r2,c2};
    }
}
🥦 运行结果

时间复杂度:O(M*M*N)
【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

空间复杂度:O(N)
【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】文章来源地址https://www.toymoban.com/news/detail-462331.html

到了这里,关于【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(49)
  • LeetCode_动态规划_中等_918.环形子数组的最大和

    给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空子数组的最大可能和。 环形数组意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。 子数组最多只能包含固定缓冲区 nums 中的每个元素

    2024年02月09日
    浏览(42)
  • 最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768)

    来源 OpenJudge - 1768:最大子矩阵 题目描述 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如,如下4 * 4的矩阵  0        -2        -7        0  9         2        -6        2 -4      

    2024年04月26日
    浏览(41)
  • 【LeetCode: 53. 最大子数组和 | 暴力递归=>记忆化搜索=>动态规划 | 分治法 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2023年04月21日
    浏览(95)
  • 【LeetCode: 410. 分割数组的最大值 | 暴力递归=>记忆化搜索=>动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月10日
    浏览(42)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(53)
  • LeetCode 面试打卡 4: 动态规划 - DataWhale 导学

    动态规划代码实现需要注意的问题 数组 dp 的初始化大小不正确 ,需要根据题目中所给的数据确定好dp数组的大小。一般为[m,n]即可 数组 dp 的初始化逻辑有误 :根据题目条件,初始化dp数组 状态转移方程不正确 :根据题目中的变量设定状态转移方程。 121. 买卖股票的最佳时

    2024年04月24日
    浏览(38)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • 【leetcode刷题之路】面试经典150题(8)——位运算+数学+一维动态规划+多维动态规划

    20 位运算 20.1 【位运算】二进制求和 题目地址:https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2envId=top-interview-150   按位逆序运算。 20.2 【位运算】颠倒二进制位 题目地址:https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2envId=top-interview-150   详见代码

    2024年04月16日
    浏览(75)
  • LeetCode_动态规划_中等_1749.任意子数组和的绝对值的最大值

    给你一个整数数组 nums 。一个子数组 [nums l , nums l+1 , …, nums r-1 , nums r ] 的 和的绝对值 为 abs(nums l + nums l+1 + … + nums r-1 + nums r ) 。请你找出 nums 中和的绝对值 最大的任意子数组(可能为空),并返回该最大值。 abs(x) 定义如下: 如果 x 是负整数,那么 abs(x) = -x 。 如果 x 是非

    2024年02月13日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包