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

概述连续子数组的最大和PythonO(n)O(n)O(n)解法题目题目链接：https://www.acwing.com/problem/content/d 连续子数组的最大和 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种:

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

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

输入三个变量

l = len(nums) # 数组长度，用于后续遍历使用s = max(nums) # 和为数组最大值，最大值的目的是防止数组元素全负导致出0b = 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 = bprint(s)

总结

以上是内存溢出为你收集整理的AcWing 连续子数组的最大和 Python O(n)解法全部内容，希望文章能够帮你解决AcWing 连续子数组的最大和 Python O(n)解法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。