首页 > 其他分享 >[leetcode]53_最大子数组(序列)和

[leetcode]53_最大子数组(序列)和

时间:2024-09-29 18:54:36浏览次数:12  
标签:cur nums max sum 53 result 数组 leetcode dp

给定一个整数数组 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
-10^4 <= nums[i] <= 10^4

解题思路:【贪心】

局部最优:
当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。
全局最优:
选取最大“连续和”
class Solution:
    def max_sum_greedy(self, nums):
        result = nums[0]
        cur_sum = 0
        for x in nums:
            cur_sum += x
            if cur_sum > result:
                result = cur_sum
            if cur_sum <= 0:
                cur_sum = 0
        return result

if __name__ == "__main__":
    nums = list(map(int, input().split(',')))
    solution = Solution()
    result = solution.max_sublist_sum(nums)
    print(result)

若需要打印数组,可以稍作改变

    def max_sum_greedy(self, nums):
        result = float('-inf')  #存储最大和
        cur_sum = 0

        max_sublist= []    #存储和序列
        max_sublist_index = []  #首尾存储区间下标

        for i in range(len(nums)):
            cur_sum += nums[i]
            #   取区间累计的最大值(相当于不断确定最大子序终止位置)
            if cur_sum >= result:
                max_sublist_index.append(i)
                result = cur_sum
            #   相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
            if cur_sum <= 0:
                max_sublist_index.clear()
                cur_sum = 0
        #   中间可能存在负数,故仅存储正数下标
        for i in range(max_sublist_index[0], max_sublist_index[-1] + 1):
            max_sublist.append(nums[i])

        return max_sublist

其他思路:【动态规划】

dp[i]表示i个元素前的最大连续和
dp[i] = max(dp[i - 1] + nums[i], nums[i])
    def max_sum_dp(self, nums):
        if len(nums) == 0:
            return 0
        dp = [None] * len(nums)
        result = dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            result = max(result, dp[i])
        return result

其他思路:【暴力解法】

    def max_sum_violence(self, nums):
        result = nums[0]
        for i in range(len(nums)):
            cur_sum = 0
            for j in range(i, len(nums)):
                cur_sum += nums[j]
                result = max(result, cur_sum)  # 更新最大值
        return result

仅作为代码记录,方便自学自查自纠

标签:cur,nums,max,sum,53,result,数组,leetcode,dp
From: https://blog.csdn.net/weixin_45653183/article/details/142620329

相关文章

  • [USACO03Open] Lost Cows(二分加树状数组)
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • P3368 【模板】树状数组 2
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • 杂:某两道依赖数组长度为 2^{k} 的杂题
    问题1:给定序列\(a_0,a_1,a_2,\cdots,a_n\)满足\(n-1=2^{k}(k\geq0)\)。定义\(R_{i}\)为\(i\)的\(k\)位的无符号二进制反转。输出\(a_{R_{0}},a_{R_{1}},a_{R_{2}},\cdots,a_{R_{n-1}}\)。题解:首先考虑如何得到\(R_{i}\)。对二进制下标使用微......
  • P10589 楼兰图腾(树状数组)
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • 【LeetCode Hot 100】22. 括号生成
    题目描述要求生成所有“合法”的括号字符串,就首先需要弄清楚括号字符串的合法性定义,也就是说如果我们现在有一个由小括号组成的字符串,该如何判断其是否符合要求。此前做过判断括号串是否合法的题目,那道题目中一般在遍历过程中维护一个栈,因为每个后括号都需要在已经遍历的子串中找......
  • Leetcode 887. 鸡蛋掉落
    1.题目基本信息1.1.题目描述给你k枚相同的鸡蛋,并可以使用一栋从第1层到第n层共有n层楼的建筑。已知存在楼层f,满足0<=f<=n,任何从高于f的楼层落下的鸡蛋都会碎,从f楼层或比它低的楼层落下的鸡蛋都不会破。每次操作,你可以取一枚没有碎的鸡蛋并把它从任一楼层......
  • JS数组指针prev、current、next的实现方式,涉及是否删除当前元素的情况分析
    背景由于业务,需要做一个循环切换的轮播图效果,循环展示列表中的每个item,但是由于切换(从左往右移动,遇到末尾则跳到开头)的过程中可能会删掉当前元素,所以需要更新下标后再切换。由于涉及到几个临界条件,这里列出来处理方式,以便后续参考。代码这里给出的简化过后的代码:<template>......
  • (nice!!!)LeetCode 2286. 以组为单位订音乐会的门票(线段树)
    题目:2286.以组为单位订音乐会的门票思路:线段树做法。(线段树)acwing1265.数星星classBookMyShow{public: //结构体typedefstructNode{intmn=0;//最小空位编号longlongsum=0;//非空位置之和}node; //n,mintN,M;......
  • 【AHK】打造炒股利器系列——用数组和循环来简化语音报时器
    上一篇文章,【AHK】打造炒股利器系列——语音报时器作为AHK入门,讲解了注释、赋值、if语句、逻辑运算符、定时器等基本知识。本篇将引入Array和Loop语句来简化化这个语音报时器,让代码更优雅,代码越简单越不容易出错误,老话说秃头上的虱子明摆着嘛。简化说明:我们用两个数组......
  • 算法训练营第二天| 209.长度最小的子数组、59.螺旋矩阵II
    209.长度最小的子数组状态:没写出来->确认自己的想法是对的之后写出来了!!!初始思路:因为子数组是连续的,所以可以采用滑动窗口,我把这个窗口设置为左闭右闭,所以初始左右边界为0。之后先移动右指针,使得找到第一个和大于等于target的子数组,记录其长度,之后再移动左指针一位,再找第二个......