53 最大子序和

01

题目信息

题目地址:https://leetcode-cn.com/problems/maximum-subarray/

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

示例:

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

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

02

解法一:动态规划

首先我们去划分一下子问题。整个数列的最大子序和,他是可能就等于n-1的最大子序和,它也可以是个新的值。至少是这两种情况

情况一:

[-1,3,1,-4,1]
当前数列的最大子序和就是4也就是(1,2)项。
它也是前n-1项的最大子序和

情况二:

[-1,3,1,-4,5]
当前数列的最大子序和是5也就是(4)项
而前n-1项的数列最大子序和还是4也就是(1,2)项

每次往后迭代一个值它的结果可能变化也可能不变化,这就是记录的点。我们算出当前最大的值然后与之前的result进行比较可能更新result也可能不变,进行下个迭代再次算当前最好的值再与result比较。

那么唯一的问题就是当前的最大值是怎么计算的,就是我们不是去暴力全部序列,而是跳过不必要的,即当前面sum为负的时候,即使后面有大的也没必要加上负的,也就是直接跳序列的首指针来达到减少遍历吃次数

[2,-1,-3,-4,7]
我们大概需要四个变量
result = 0 // 结果
i = 0 // 序列的首指针
j = 0 // 序列的尾指针
sum = 0 //当前序列和

但我们记录sum就代表i至j了,所以不用指针变量 代码如下:

public int maxSubArray(int[] nums) {
    //sum表示上一个最大子序和也就是dp[n-1]
    int sum = 0;
    int result = nums[0];
    for(int i = 0; i < nums.length; i++){
        sum = sum > 0 ? sum + nums[i] : nums[i];
        max = max > sum ? max : sum;
    }
    return max;
}

03

总结

这题的话虽然是简单但还是要点思考的,用到了动态与贪心的思想合起来减少了遍历一遍的次数。关于自顶向下的分治比较适合之后筹备的另一个系列做例子这里不展开。

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-02-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 53. 最大子序和

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

    Michel_Rolle
  • 53. 最大子序和

    CaesarChang张旭
  • 【Leetcode】53. 最大子序和

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

    Leetcode名企之路
  • LeetCode 53. 最大子序和

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

    freesan44
  • leetcode题解-53.最大子序和

    Given an integer array nums, find the contiguous subarray (containing at least o...

    编程珠玑
  • 画解算法:53. 最大子序和

    https://leetcode-cn.com/problems/maximum-subarray/

    灵魂画师牧码
  • LeetCode每日一题53: 最大子序和

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

    benny
  • LeetCode 53. 最大子序和(动态规划)

    题目链接:https://leetcode-cn.com/problems/maximum-subarray/ 《剑指Offer》同题:面试题42. 连续子数...

    Michael阿明
  • ​LeetCode刷题实战53:最大子序和

    https://leetcode-cn.com/problems/maximum-subarray/

    程序IT圈
  • 每天手撕一道算法-53. 最大子序和

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

    编程之心
  • LeetCode 53.最大子序列和 - JavaScript

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

    心谭博客
  • LeetCode 53题 最大子序和 -- JavaScript

    该题是在一个整数数组中找到一个和最大的连续子数组,并返回和值。那么如何找到一个和最大的连续子数组呢?我们知道,这肯定需要遍历数组才行;好,那我们就开始遍历数组。...

    IT人一直在路上
  • 53. 最大子序和 Krains 2020-08-20 10:46:24 动态规划前缀和

    看到子数组的题目,就应该想到前缀和,为了最大化子数组的和,假设我们有前缀和s,为了让子数组和最大,我们应该找出[i, j],使得s[j+1]-s[i]的差值最大...

    Krains
  • Leetcode#53.Maximum Subarray(最大子序和)

    题目描述 给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。 例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4...

    武培轩
  • 最大子序和

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

    木子星兮
  • 最大子序和

    这道题就是 Leetcode 的第 53 题-最大子序和,了解「动态规划」的童鞋,在看到最大两个字的时候,很容易就会想到用「动态规划」去解答,因为涉及到「最优解...

    潜行前行
  • 最大子序和

    大家好,我是来自「华为」的「小熊」。端午假期马上就要结束了,小熊给大家带来一道笔试和面试中与「动态规划」相关的常考的简单题,这道题被字节、微软、亚马逊和苹果等各...

    程序员小熊
  • [-算法篇-] 最大子序列和

    张风捷特烈
  • [leetcode数组系列]4 最大子序和

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

    我是程序员小贱

扫码关注云+社区

领取腾讯云代金券