V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
牛客网
zzzrf
V2EX  ›  推广

巨硬面试题:最大子数组

  •  
  •   zzzrf · 36 天前 · 2375 次点击
    这是一个创建于 36 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

    样例 1:

    输入:[−2,2,−3,4,−1,2,1,−5,3]
    输出:6
    解释:符合要求的子数组为[4,−1,2,1],其最大和为 6 。
    

    样例 2:

    输入:[1,2,3,4]
    输出:10
    解释:符合要求的子数组为[1,2,3,4],其最大和为 10 。
    

    在线做题地址

    算法

    贪心

    算法分析

    • 题目要求给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。若直接暴力枚举子数组,时间复杂度需要 O(N2);
    • 由于题目要求是子数组最大和,因此可以利用贪心思想,通过局部的子数组最大,进而得到整体的最优解;
    • 需要注意贪心的策略不能有后效性;

    算法步骤

    1. 定义 maxAns 记录全局最大值,即结果; sum 记录当前子数组的和;
    2. 初始化:maxAns=Integer.MIN_VALUE; sum=0; 因为数组可以全为负数,因此 maxAns 不能直接初始化为 0 ;
    3. 遍历整数数组:
    • Sum 累加当前的值;
    • 若当前 sum>maxAns,更新 maxAns=sum ;
    • 若当前 sum<0,表示当前的子数组和已经为负,累加到后面会使和更小,因此令 sum=0,相当于放弃当前的子数组,重新开始;

    复杂度

    • 时间复杂度:O(N),N 为数组长度
      • 只需要遍历一遍数组就能找到答案;
    • 空间复杂度:O(1)
      • 只需要用到 maxAns 和 sum 两个变量.
    public class Solution {
        /**
         * @param nums: A list of integers
         * @return: A integer indicate the sum of max subarray
         */
        public int maxSubArray(int[] nums) {
    
            // maxAns 记录全局最大值 sum 记录当前子数组的和
            int maxAns = Integer.MIN_VALUE, sum = 0;
            // 贪心
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                maxAns = Math.max(maxAns, sum);
                sum = Math.max(sum, 0);
            }
    
            return maxAns;
        }
    }
    
    19 条回复    2020-09-15 16:02:06 +08:00
    xhxhx
        1
    xhxhx   36 天前
    动态规划
    Dabaicong
        2
    Dabaicong   36 天前
    [−2,2,−3,4,−1,2,1,−5,3] 最大值不应该是 12 么,子数组是[2,4,2,1,3] ,
    gromit1337
        3
    gromit1337   36 天前
    @Dabaicong #2 他没说清楚子数组要连着
    tikazyq
        4
    tikazyq   36 天前
    用 HashMap 不行么?
    YueZhang
        5
    YueZhang   36 天前
    https://juejin.im/post/6844903935371804679

    我写的解析,大家可以支持下。看不明白,你找我
    Dabaicong
        6
    Dabaicong   36 天前
    差点看的自己怀疑智商。
    Dabaicong
        7
    Dabaicong   36 天前
    @gromit1337 了解了。那 dp 就是标准解法,时间 O(N)
    8Cangtou
        8
    8Cangtou   36 天前
    func maxSubArray(nums []int) int {
    if len(nums) == 1{
    return nums[0]
    }
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    res := nums[0]
    for i := 1;i < len(nums); i++{
    dp[i] = max(dp[i-1] + nums[i], nums[i])
    res = max(res, dp[i])
    }
    return res
    }

    func max(a, b int) int{
    if a > b{
    return a
    }
    return b
    }
    amaranthf
        9
    amaranthf   36 天前
    这个贪心的解释无法理解……似乎是 dp 的一种简化形式?
    ericgui
        10
    ericgui   36 天前
    @Dabaicong 你肯定排序了,哈哈,我也遇到过这个问题
    Goldilocks
        11
    Goldilocks   36 天前
    这不是算法导论课本的正文例子吗?
    usingnamespace
        12
    usingnamespace   36 天前
    这特么是最最最最最简单的 dp 了吧....开始还以为是子序列的,还稍微麻烦点,子数组这种真是太入门级别简单了,用两个变量也是很简单的一维 dp 优化
    mahaonan1994
        13
    mahaonan1994   36 天前 via Android
    @Livid 🐶
    gygy19941221
        14
    gygy19941221   36 天前
    这叫动态规划不叫贪心......
    dp[i]表示以位置 i 为结尾的子数组和最大值,如果 dp[i-1]小于 0,则 dp[i] = arr[i]。如果 dp[i-1]大于 0,则 dp[i]=dp[i-1]+arr[i]。这是状态转移方程。
    然后观察发现计算 dp[i]只需要 dp[i-1]这个状态,因此可以只用一个变量反复更新新的 dp[i-1]的值,不需要用 dp 数组存储之前的每一个状态,能降低空间。
    est
        15
    est   36 天前   ❤️ 1
    忘记贴公众号 推广二维码了?
    ccagml
        16
    ccagml   36 天前 via Android   ❤️ 1
    哪里可以知道楼主的推广二维码呢
    Livid
        17
    Livid   V2EX Moderator   36 天前
    @zzzrf 下次请把这样的主题发到 /go/promotions

    这次我们已经为你移动。

    请阅读 V2EX 的节点使用说明:

    https://www.v2ex.com/help/node
    nvioue
        18
    nvioue   36 天前
    1 分不清贪心和 dp
    2 不解释 “子数组” 的具体定义, 连续还是不连续?
    3 带上巨硬干什么 ? flaamg 一般不考原题的吧

    https://leetcode.com/problems/maximum-subarray/
    liukangxu
        19
    liukangxu   36 天前
    为啥每次都要碰瓷巨硬?
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1094 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 22:35 · PVG 06:35 · LAX 15:35 · JFK 18:35
    ♥ Do have faith in what you're doing.