AcWing 连续子数组的最大和 Python O(n)解法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了AcWing 连续子数组的最大和 Python O(n)解法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1579字，纯文字阅读大概需要3分钟。

内容图文

连续子数组的最大和 Python O ( n ) O(n) O(n)解法

题目

题目链接：https://www.acwing.com/problem/content/description/50/

题目描述

输入一个非空整型数组,数组里的数可能为正,也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O ( n ) O(n) O(n)。

样例

输入:[1, -2, 3, 10, -4, 7, 2, -5]

输出:18

解题

思路分析

本题的常规解题路线有3种:

1. 暴力枚举，优化后时间复杂度为 O ( n 2 ) O(n^2) O(n2)
2. 分治，分别考虑字串在左边、字串在中间、字串在右边三种情况，时间复杂度为 O ( n l o g n ) O(nlog n) O(nlogn)
3. 动态规划，也就是本题要讲的一种方法，时间复杂度为 O ( 1 ) O(1) O(1)

常规解法很容易想到，也很容易做出来，但是由于需要两个for循环嵌套，所以其时间复杂度为 O ( n 2 ) O(n^2) O(n2)，不满足本题的要求。故本题使用动态规划法。

输入三个变量

l = len(nums) # 数组长度，用于后续遍历使用
s = max(nums) # 和为数组最大值，最大值的目的是防止数组元素全负导致出0
b = 0 # 初始化变量

开始遍历

对b进行判断

• 如果b>0：说明当前这个子串有可能是最大的，那就继续加上第i项；
• 如果b<=0：说明当前这个字串和为负，那就没有比较的意义了，将b初始化为第i项
• 最后判断b>s?
  • 如果b大于s，则更新s的值为b

最后输出s的结果即可

代码实现

AcWing答题模式代码

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums) # 数组长度
        s, b = max(nums), 0 # 初始化最大和，子段和
        for i in range(0, l):
            if b > 0: # 判断子段和的值
                b += nums[i]
            else:
                b = nums[i]
            if b > s:
                s = b
        return s

普通模式代码

nums = eval(input()) # 从控制台读取数组，格式为[1,2,3,...]
l = len(nums) # 数组长度
s, b = max(nums), 0 # 初始化最大和，子段和
for i in range(0, l):
    if b > 0: # 判断子段和的值
        b += nums[i]
    else:
        b = nums[i]
    if b > s:
        s = b
print(s)

内容总结

以上是互联网集市为您收集整理的AcWing 连续子数组的最大和 Python O(n)解法全部内容，希望文章能够帮你解决AcWing 连续子数组的最大和 Python O(n)解法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端