首页 > 其他分享 >一道题把我气笑了:) 力扣.53 最大子数组和 leetcode maximum-subarray

一道题把我气笑了:) 力扣.53 最大子数组和 leetcode maximum-subarray

时间:2024-11-10 17:41:15浏览次数:3  
标签:nums int maximum 53 力扣 数组 maxSum dp

数组系列

力扣数据结构之数组-00-概览

力扣.53 最大子数组和 maximum-subarray

力扣.128 最长连续系列 longest-consecutive-sequence

力扣.1 两数之和 N 种解法 two-sum

力扣.167 两数之和 II two-sum-ii

力扣.170 两数之和 III two-sum-iii

力扣.653 两数之和 IV two-sum-IV

力扣.015 三数之和 IV three-sum

题目

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

子数组是数组中的一个连续部分。

示例 1:

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

输入:nums = [1]
输出:1
示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

1 <= nums.length <= 10^5
-104 <= nums[i] <= 10^4

进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

v1-前缀和 BF

思路

看到连续子数组和,比较自然的是想到用前缀和来加速子数组和的计算。

1)构建好前缀和

2)穷举所有可能的子数组和,找出最大值。

实现

class Solution {
    public int maxSubArray(int[] nums) {
        final int n = nums.length;

        int[] prefixSum = new int[n];
        prefixSum[0] = nums[0];
        for(int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i];
        }

        // BF 匹配
        int maxSum = nums[0];
        for(int i = 0; i < n; i++) {
            // 后面的数组 》 前一个标识
            for(int j = i; j < n; j++) {
                int sum = prefixSum[j] - prefixSum[i] + nums[i];

                // 更新最大值
                 maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

效果

超出时间限制

204 / 210 个通过的测试用例

v2-如何改进? 双指针?

思路

我们之所以很慢,是因为在计算连续子数组和的时候,计算了各种场景。但是这里要如何优化呢?

但是不对比所有的,如何找到最大的呢?

最气人的是题目中的那一句:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

左右两边的双指针可行吗?

感觉双指针不可行 双指针适合计算最大的长度,但是不太适合这种最大的和。

v3-贪心

思路1

看了一眼相似题目,其中有一个是 【买卖股票的最佳时机】{简单}

于是贪心的话,思路可以简化为:

public int maxSubArray(int[] nums) {
    final int n = nums.length;
    // BF 匹配
    int maxSum = nums[0];
    for(int i = 1; i < n; i++) {
        // 加上当前值变大?不加当前值?
        // 变大
        int num = nums[i];
        // 无脑直接加
        if(num >= 0) {
            maxSum += num;
        } else {
            // 如果不是呢?
            // 也不能贸然丢弃 因为连续起来,后来可能又大于0的?
            // 那么 怎么简单的判断这个事情呢?
            
        }
    }
    return maxSum;
}

思路-打开评论区

首先看到一首打油诗 被逗笑了

打开我的题库,调为简单难度。

计算最大子数,直接给我难住。

报错铺满屏幕,凝望没有思路。

缝缝补补做出,击败零个用户。

翻阅评论找补,令我勃然大怒。

不禁心有一问,都是人,凭什么我——这么废物。

55555555

被打开的不单单是评论区的,当然还有自己的思路。

我们整体的方向没错,但是这里需要一个技巧。

如下:

/**解题思路

用 temp 记录局部最优值,用 result 记录全局最优值。
每遍历一个新元素时,判断(已遍历的连续子数组的和)加上(当前元素值),与(当前元素值)对比谁更大。
(1)如果已遍历的连续子数组的和 + 当前元素值 >= 当前元素值
说明(已遍历的连续子数组的和)是大于等于0的,令 temp = 已遍历的连续子数组的和 + 当前元素值。

(2)如果已遍历的连续子数组的和 + 当前元素值 < 当前元素值
说明(已遍历的连续子数组的和)是小于0的,加上这部分只会拖累当前元素,故应该直接抛弃掉这部分,令 * temp = 当前元素值。

(3)对比 temp 和 result,如果 temp 更大,则更新到 result 中。 
*/

代码

class Solution {
    public int maxSubArray(int[] nums) {
        final int n = nums.length;

        // BF 匹配
        int maxSum = nums[0];
        int tempSum = nums[0];
        for(int i = 1; i < n; i++) {
            int num = nums[i];

            // 历史数据大于等于0,则保留继续累加
            if(tempSum >= 0) {
                tempSum += num;
            } else {
                // 历史和小于 0,直接舍弃。只保留今天
                tempSum = num;
            }

            maxSum = Math.max(maxSum, tempSum);
        }

        return maxSum;
    }
}

简单的优化,我们直接判断是否大于等于0即可,减少一次累加计算。聊胜于无。

效果

1ms 100%

效果拔群

小结

那么这一题和股票有啥关系呢?

股票的买卖贪心其实要简单一些,就是明天比今天高,直接无脑买卖。而且不要求连续。

这里要求连续,就需要一个巧妙的构思,有时候不一定能很快想到。

比如我们可买卖股票无限次数上点难度,增加一个限制,买卖的天数必须是连续的天数,怎么解?

其实就是 {买+卖} 的和当做一个数,然后就变成这一题了

v3-DP

思路

一个问题能不能被 DP 解决呢?

就看能不能拆分为递推的子问题。

那么,这个问题可以吗?

递推公式是什么?

也就是我们还是需要想到上面那个思路。

dp[i] = Math.max(0, dp[i-1]) + nums[i];

实现

class Solution {
    public int maxSubArray(int[] nums) {
        final int n = nums.length;

        int[] dp = new int[n];
        dp[0] = nums[0];
        int maxResult = nums[0];
        for(int i = 1; i < n; i++) {
            int num = nums[i];
            dp[i] = Math.max(0, dp[i-1]) + nums[i];
            maxResult = Math.max(dp[i], maxResult);
        }

        return maxResult;
    }
}

效果

2ms 36.91%

小结

DP 的优点是使用范围更加广泛,这如果是一个系列的题目,不断上难度,DP 也许可以成为一个模板。

但是如果是性能,比不上上面的 greedy。

或者说上面的贪心,是对下面递推数组的存储空间优化。

差点挂在了第一个选择的数组题目上....ORZ

标签:nums,int,maximum,53,力扣,数组,maxSum,dp
From: https://www.cnblogs.com/houbbBlogs/p/18538244

相关文章

  • SQL,力扣题目1159,市场分析 II
    一、力扣链接LeetCode_1159二、题目描述表: Users+----------------+---------+|ColumnName|Type|+----------------+---------+|user_id|int||join_date|date||favorite_brand|varchar|+----------------+---------+us......
  • SQL,力扣题目262,行程和用户
    一、力扣链接LeetCode_262二、题目描述表:Trips+-------------+----------+|ColumnName|Type|+-------------+----------+|id|int||client_id|int||driver_id|int||city_id|int||status|enum......
  • 45-best-time-to-buy-and-sell-stock-with-cooldown 力扣 714. 买卖股票的最佳时机包
    买卖股票系列【leetcode】40-best-time-to-buy-and-sell-stock力扣121.买卖股票的最佳时机【leetcode】41-best-time-to-buy-and-sell-stock-ii力扣122.买卖股票的最佳时机II【leetcode】42-best-time-to-buy-and-sell-stock-iii力扣123.买卖股票的最佳时机II......
  • 力扣题库Day3(持续更新中...)
    2024/11/10x的平方根:要求:给你一个非负整数 x ,计算并返回 x 的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去。注意:不允许使用任何内置指数函数和算符,例如 pow(x,0.5) 或者 x**0.5 。classSolution{publicintmySqrt(......
  • [LeetCode] 3090. Maximum Length Substring With Two Occurrences
    Givenastrings,returnthemaximumlengthofasubstringsuchthatitcontainsatmosttwooccurrencesofeachcharacter.Example1:Input:s="bcbbbcba"Output:4Explanation:Thefollowingsubstringhasalengthof4andcontainsatmosttw......
  • 代码随想录算法训练营第18天| 530.二叉搜索树的最小绝对差, 501.二叉搜索树中的众数 , 2
    530.二叉搜索树的最小绝对差文章链接:https://programmercarl.com/0530.二叉搜索树的最小绝对差.html视频链接:https://www.bilibili.com/video/BV1DD4y11779/?vd_source=6cb513d59bf1f73f86d4225e9803d47b题目链接:https://leetcode.cn/problems/minimum-absolute-difference-in......
  • [LeetCode] 2841. Maximum Sum of Almost Unique Subarray
    Youaregivenanintegerarraynumsandtwopositiveintegersmandk.Returnthemaximumsumoutofallalmostuniquesubarraysoflengthkofnums.Ifnosuchsubarrayexists,return0.Asubarrayofnumsisalmostuniqueifitcontainsatleastmdisti......
  • 力扣(LeetCode)106. 从中序与后序遍历序列构造二叉树
    一、目标  给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。二、代码分析总体代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*int......
  • 104.力扣(leetcode)二叉树的最大深度(JAVA)
    一、目标给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。二、代码分析总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeN......
  • 力扣(Leetcode)112. 路径总和(JAVA)
    一、目标 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。叶子节点 是指没有子节点的节点。二、代码解读......