本文主要是介绍AcWing 连续子数组的最大和 Python O(n)解法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

连续子数组的最大和 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)解法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！