精华内容
下载资源
问答
  • 文章目录【LeetCode连续子数组、子矩阵最大和问题连续子数组最大和★最大子矩阵★★★最大黑方阵★★ 连续子数组最大和★ 剑指 Offer 42. 连续子数组最大和 【题目】输入一个整型数组,数组中的一个或连续多...

    【LeetCode】连续子数组、子矩阵最大和问题

    连续子数组的最大和★

    剑指 Offer 42. 连续子数组的最大和

    题目】输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

    要求时间复杂度为O(n)

    提示:

    • 1 <= arr.length <= 10^5
    • -100 <= arr[i] <= 100

    示例

    输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6

    解题思路

    方法一:

    动态规划,空间复杂度O(n)

    class Solution {
        public int maxSubArray(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int res = dp[0];
            for (int i = 1; i < nums.length; i++) {
                //保证和是连续的
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }
    

    方法二:空间复杂度O(1)

    class Solution {
        public int maxSubArray(int[] nums) {
            int dp = nums[0];
            int res = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (dp >= 0) {
                    dp += nums[i];
                } else {
                    dp = nums[i];
                }
                if (dp > res) res = dp;
            }
            return res;
        }
    }
    

    最大子矩阵★★★

    面试题 17.24. 最大子矩阵

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

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

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

    说明:

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

    示例

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

    解题思路

    上一题是一维求最大和,这一题是二维求最大和。显然可以通过转换来将二维映射为一维。

    使用一个数据sums来保存当前i行至j行的列元素之和,求最大值并保存下标即可。

    class Solution {
        public int[] getMaxMatrix(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[] pos = new int[4];
            int res = Integer.MIN_VALUE, dp = 0;
            int[] sums = new int[n];
            int begin_r = 0, begin_c = 0;
    
            for (int i = 0; i < m; i++) {
                Arrays.fill(sums, 0);
                for (int j = i; j < m; j++) {
                    dp = 0;
                    for (int k = 0; k < n; k++) {
                        sums[k] += matrix[j][k];
                        if (dp > 0) {
                            dp += sums[k];
                        } else {
                            dp = sums[k];
                            begin_r = i;
                            begin_c = k;
                        }
                        if (dp > res) {
                            res = dp;
                            pos[0] = begin_r;
                            pos[1] = begin_c;
                            pos[2] = j;
                            pos[3] = k;
                        }
                    }
                }
            }
            
            return pos;
        }
    }
    

    最大黑方阵★★

    面试题 17.23. 最大黑方阵

    题目】给定一个方阵,其中每个单元(像素)非黑即白。设计一个算法,找出 4 条边皆为黑色像素的最大子方阵。

    返回一个数组 [r, c, size] ,其中 r, c 分别代表子方阵左上角的行号和列号,size 是子方阵的边长。若有多个满足条件的子方阵,返回 r 最小的,若 r 相同,返回 c 最小的子方阵。若无满足条件的子方阵,返回空数组。

    提示:

    • matrix.length == matrix[0].length <= 200

    示例

    输入:
    [
       [1,0,1],
       [0,0,1],
       [0,0,1]
    ]
    输出: [1,0,2]
    解释: 输入中 0 代表黑色,1 代表白色,标粗的元素即为满足条件的最大子方阵
    

    解题思路

    使用二维数组left保存左边连续0个数

    使用二维数组top保存上面连续0个数,

    若当前位置左边和上边连续0个数均大于暂时结果res[2],则判断其黑方阵另外两条边是否符合要求

    class Solution {
        public int[] findSquare(int[][] matrix) {
            if (matrix == null) return null;
            int n = matrix.length;
            if (n == 1 && matrix[0][0] == 1) return new int[]{};
            if (n == 1 && matrix[0][0] == 0) return new int[]{0, 0, 1};
    
            int[][] left = new int[n + 1][n + 1];
            int[][] top  = new int[n + 1][n + 1];
            int[] res = new int[3];
            int sz = 0;
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        left[i + 1][j + 1] = left[i + 1][j] + 1;
                        top[i + 1][j + 1]  = top[i][j + 1] + 1;
                        sz = Math.min(left[i + 1][j + 1], top[i + 1][j + 1]);
                        if (sz > res[2]) {
                            int r = i - sz + 1;
                            int c = j - sz + 1;
                            while (sz > res[2]) {
                                if (left[r + 1][j + 1] >= sz && top[i + 1][c + 1] >= sz) {
                                    res[0] = r;
                                    res[1] = c;
                                    res[2] = sz;
                                    break;
                                }
                                sz--;
                                r++;
                                c++;
                            }
                        }
                    }
                }
            }
    
            return res[2] == 0 ? new int[]{} : res;
        }
    }
    
    展开全文
  • leetcode-连续子数组最大和 题目链接:添加链接描述 给定一个数组,寻找出其中的和最大连续子数组 这是一个DP的题目,不过他的DP比较简单。首先,使用dp[i]表示前i位(包含第i位)的子数组最大和,我们会发现,...

    leetcode-连续子数组的最大和
    题目链接:添加链接描述
    给定一个数组,寻找出其中的和最大的连续子数组
    这是一个DP的题目,不过他的DP比较简单。首先,使用dp[i]表示前i位(包含第i位)的子数组最大和,我们会发现,nums[i]是否加上取决于前面的dp[i]是否为正数,如果是负数的话,没必要加上去,由nums[i]重新开始,向后延伸即可,如果是正数,则可以加上,因为这个对于最终的子数组和最大,是有好处的,所以来说,编码方式就很明显了。

    class Solution {
        public int maxSubArray(int[] nums) {
            int res = nums[0];
        	for(int i = 1; i < nums.length; i++){
        		if(nums[i-1]>=0) {
        			//如果前面的子数组和会对后面的结果产生增长的效果
        			//就加进去
        			nums[i] = nums[i-1] + nums[i];
        		}
        		if(res < nums[i]) {
        			//更新最大值
        			res = nums[i];
        		}
        	}
        	return res;
        }
    }
    
    展开全文
  • 53 maximum-subarray 题目 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其...以nums[i]为结尾的连续子数组最大和,要么是 以nums[i-1]为结尾的连续子数组最大和+num...

    53 maximum-subarray

    题目
    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    示例:
    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

    思路
    以nums[i]为结尾的连续子数组的最大和,要么是 以nums[i-1]为结尾的连续子数组最大和+nums[i],要么就是nums[i]本身。
    即sum[i] = max(sum[i-1] + nums[i], nums[i])。

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if(nums.size() == 0)
                return 0;
            int max_sum = nums[0], sum = nums[0];
            for(int i=1;i<nums.size();i++)
            {
                sum = max(sum + nums[i], nums[i]);
                max_sum = max(max_sum, sum);
            }
            return max_sum;
        }
    };
    

    分治方法
    主要的思路就是将当前数组分成两份,(start, i)(i+1, end)分别计算,并且还有一种情况就是包含了i和i+1的和,取三者最大值即可。时间复杂度是O(NlogN)。

    展开全文
  • 连续子数组最大和>>> 动态规划:dp[i]为数组中0-i个数中连续数组子数组最大和,状态转移方程:dp[i]=max(dp[i-1]+nums[i],nums[i]),初始值dp[0]=nums[0] package BDyNamicProgramming; /** * @Author...

    连续子数组最大和>>>
    在这里插入图片描述

    动态规划:dp[i]为数组中0-i个数中连续数组子数组最大和,状态转移方程:dp[i]=max(dp[i-1]+nums[i],nums[i]),初始值dp[0]=nums[0]

    
    package BDyNamicProgramming;
    
    /**
     * @Author Zhou  jian
     * @Date 2020 ${month}  2020/4/21 0021  15:53
     */
    public class Problem42 {
    
        //采用前缀和
        //双层循环超出时间限制:时间复杂度为O(N^2)
        public int maxSubArray(int[] nums) {
            if(nums.length==1) return nums[0];
            int[] sum = new int[nums.length+1];
            int maxSum = Integer.MIN_VALUE;
            sum[0]=0;
            //求的前缀和
            for(int i=0;i<nums.length;i++){
                sum[i+1]=sum[i]+nums[i];
            }
    
            for(int i=0;i<nums.length+1;i++){
                for (int j=0;j<i;j++){
                    if(sum[i]-sum[j]>maxSum) maxSum=sum[i]-sum[j];
                }
            }
            return maxSum;
        }
    
    
        /**
         *
         * @param nums
         * @return
         * 动态规划:
         *          状态定义:设动态规划列表dp,dp[i]代表以元素nums[i]为结尾的连续数组最大和
         *                  为何定义最大和dp[i]中必须包含元素nums[i]:保证dp[i]递推到dp[i+1]的正确性
         *
         *           转移方程:若dp[i-1]<=0说明dp[i-1]对dp[i]产生负贡献,即dp[i-1]+nums[i]还不如nums[i]本身大
         *
         *                     dp[i-1]>0时:执行dp[i]=dp[i-1]+nums[i]
         *                     dp[i-1]<=0时:执行dp[i]=nums[i]
         *
         *          初始状态:dp[0]= nums[0] 即以nums[0]结尾的连续子数组最大和为nums[0]
         *
         *          返回值:返回dp列表中的最大值,代表全局最大值
         */
    
        //空间复杂度降低:由于dp[i]只与dp[i-1]和nums[i]有关系,因此
        //可以将原数组nums用作dp列表,即直接在nums上修改即可
        //由于省去dp列表使用额外的空间因此空间复杂度从O(N)到O(10
        public int maxSubArray1(int[] nums){
    
            int[] dp = new int[nums.length];
    
            dp[0]=nums[0];
            int max = dp[0];
            for(int i=1;i<nums.length;i++){
    
                //根据前一个的dp值确定当前位置的dp
                if(dp[i-1]<=0) dp[i]=nums[i];
                else dp[i]=dp[i-1]+nums[i];
    
                if(dp[i]>max) max=dp[i];
            }
            return max;
        }
    
    
    
    
        public static void main(String[] args) {
    
        }
    
    
    
    
    
    
    }
    
    
    
    展开全文
  • 题目: 给你一个整数数组 nums ,请你找出数组中乘积最大连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2:...
  • 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示: 1 <= arr.length <= 10^5 -100 <= arr[i] <= 100 思路: 遍历数组,因为当一个负数加上任意数,都会比这个数本身小。 所以可以从nums
  • 题目:连续子数组最大和 /* 思路:假设现在遍历到下标为K的数,这时我们需要比较 K数是否比 K之前数的和+K数 大,如果是 则说明K之前数的和肯定是负数,那么我们下次就从K下标开始算起 , 如果不是 那么就继续加...
  • 题目来源:力扣 题目描述: 输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。...解释: 连续子数组 [4,-1,2,1] 的和最...
  •   使用动态规划,子问题:局部数字构成的数组的最大连续和,转移方程F(i)=max(F(i-1)+a[i],a[i]),初始状态:F(0)=a[0],如果想要求n个数组中的最大连续子数组的和,就要先求前n-1个,用前n-1个同n个进行判断,取...
  • 连续子数组最大和 输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 class Solution { public: int maxSubArray(vector...
  • 问题描述: 输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一...解释:连续子数组[4,-1,2,1] 的和最大,为6。 算法分析: 本题可以使用动态规划解决。动态规划方法也可以认为是填表法...
  • 连续子数组最大和 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,...
  • (1) dp[i]:以第i项结束的最大和,答案是dp[i]中的最大值,所以要求两次最值!!! (2) dp[i] = max(dp[i-1] + nums[i], nums[i]); dp[i-1] < 0时,dp[i] = nums[i]; dp[i-1] > 0时,dp[i] = dp[i-1] + nums[i]...
  • 1. 题目 输入一个整型数组,数组中的一个或连续多个整数组成...解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 2 .题解 class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; int former =
  • 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 题目要求时间复杂度O(N),不能暴力。 可以考虑,记录前面的和,如果前一个和 <0 ,则直接抛弃它,使用自己的进行记录。每一次看这个和与最大值比较,取最大值。 ...
  • //记录包括当前数为结尾的连续子数组最大值 int imin = nums[0]; //记录包括当前数为结尾的连续子数组的最小值 for(int i = 1; i ; i++){ if(nums[i] ){ int tmp = imax; imax = imin; imin = tmp; } ...
  • Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 ...
  • LeetCode-连续子数组最大

    千次阅读 2017-03-10 14:41:36
    Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array[−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray[4,−1,2,1]...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,044
精华内容 4,817
热门标签
关键字:

leetcode最大连续子数组