子序列题目 Leetcode题目

墨蓝 2022-12-27 14:20 131阅读 0赞

1. [53. 最大子序和][53.]

[面试题 16.17. 连续数列][16.17.]

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

示例：

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

解法1: 贪心法

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            # 最大子序列和， 很重要的一个题；
            # 两种方法(1):贪心法 （2):动态规划
            # 1. 贪心法
            max_sum = nums[0]
            sum_cur = 0
            for item in nums:
                sum_cur = sum_cur + item  
                max_sum = max(max_sum, sum_cur)
                if sum_cur < 0:  # 前一个和 为负，不会有增益，直接0
                    sum_cur = 0
            return max_sum

解法2:  动态规划（Dynamic Programming, DP）

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            # 2. 动态规划  # O(n)
            nums_len = len(nums)
            for i in range(1, nums_len):  # 前一个数大于0 就加上，依次往后加， 取最大值；
                if nums[i-1] > 0:
                    nums[i] = nums[i-1] + nums[i]  # 和记录下来
            return max(nums)

[53.]: https://leetcode-cn.com/problems/maximum-subarray/
[16.17.]: https://leetcode-cn.com/problems/contiguous-sequence-lcci/

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关回溯法题目 leetcode

1. [22. 括号生成][22.] 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例：输入：n = 3

秒速五厘米/ 2022年12月31日 01:24/ 0 赞/ 97 阅读

相关子序列题目 Leetcode题目

1. [53. 最大子序和][53.] [面试题 16.17. 连续数列][16.17.] 给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含

墨蓝/ 2022年12月27日 14:20/ 0 赞/ 132 阅读

相关字典序 Leetcode题目

1. [440. 字典序的第K小数字][440. _K] 给定整数 `n` 和 `k`，找到 `1` 到 `n` 中字典序第 `k` 小的数字。注意：1 ≤ k ≤ n

太过爱你忘了你带给我的痛/ 2022年12月27日 11:27/ 0 赞/ 104 阅读

相关括号题目 Leetcode

括号系列问题 Leetcode [20. 有效的括号][20.] 给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串

约定不等于承诺〃/ 2022年10月29日 01:47/ 0 赞/ 148 阅读

相关【LeetCode】数论题目总结

一、基本问题 1. 辗转相除的gcd应用，求最大公约数，进而lcm求最小公倍数 2. 质数问题 3. 余数问题、位运算、进制转换 4. 约数定理：分解质因数.然后

r囧r小猫/ 2022年10月17日 04:23/ 0 赞/ 119 阅读

相关 leetcode部分题目（C++）

2016.3.19 88. Merge Sorted Array（从尾到头） [MySubmissions][] Question TotalAccepted:

r囧r小猫/ 2022年09月24日 12:20/ 0 赞/ 146 阅读

相关 Leetcode题目汇总

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

秒速五厘米/ 2022年09月13日 15:27/ 0 赞/ 158 阅读

相关 LeetCode 题目总结/分类

欢迎参考我的 [leetcode代码][leetcode] 利用堆栈： [http://oj.leetcode.com/problems/evaluate-rev

左手的ㄟ右手/ 2022年07月18日 01:27/ 0 赞/ 117 阅读

相关 leetcode题目解析

前言本文为[leetcode][]上的题目简单分析，仅作记录，欢迎提出建议，共同学习交流。题目的源代码和测试用例可以在[leetcodeWithC][]下载 001

妖狐艹你老母/ 2022年06月10日 00:08/ 0 赞/ 165 阅读

相关 LeetCode题目：加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会

傷城~/ 2021年12月17日 12:13/ 0 赞/ 158 阅读