算法练习——最长子数组和 leetcode.53 python

题目描述：

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

子数组 是数组中的一个连续部分。

C语言的解法可以参考 @weiambt 的这篇文章。

连续子数组的最大和问题（五种解法）_weiambt的博客-CSDN博客https://blog.csdn.net/Supreme7/article/details/117398880思路一：暴力穷举

class Solution:
    def maxSubArray(self, nums):
        length = len(nums)
        ret = nums[0]
        for i in range(0, length):  # 从i开始
            for j in range(i, length):  # 到j结束
                temp_max = 0
                for k in range(i, j+1):  # 求i到j之间的累加和
                    temp_max = temp_max + nums[k]
                ret = max(ret,temp_max)
        return ret

时间复杂度：O(n3)

思路二：动态规划（本题最常用思路）

第i个状态只与第i-1个状态有关。

告别动态规划，连刷40道动规算法题，我总结了动规的套路_Hollis Chuang的博客-CSDN博客https://blog.csdn.net/hollis_chuang/article/details/103045322?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165216164316782425139035%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165216164316782425139035&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-103045322-null-null.142^v9^control,157^v4^control&utm_term=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&spm=1018.2226.3001.4187在这篇文章中，作者总结了动态规划类问题的求解思路：（在附录中，会更新其中例题的解法：）

1、定义数组元素的含义

2、找出数组元素之间的关系式

3、找出初始值

class Solution:
    def maxSubArray(self, nums):
        length = len(nums)
        # 第一步骤：dp[i]的含义是以i结尾的数组字串的最大和
        dp = [0] * length
        # 第三步骤：初始值
        dp[0] = nums[0]
        for i in range(1,length):
            # 第二步骤：状态转移方程
            # 如果dp[i-1]为正，则也要计算前面的字串；如果dp[i-1]为负，则从i重新计算最大和
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        res = max(dp)
        return res

时间复杂度：O(n) 

 思路三：扫描法

当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。

class Solution:
    def maxSubArray(self, nums):
        res = nums[0]
        sum_temp = nums[0]
        length = len(nums)
        for i in range(1,length):
            if sum_temp < 0:
                sum_temp = nums[i]
            else:
                sum_temp += nums[i]
            res = max(res,sum_temp)
        return res

时间复杂度：O(n) 

附录：

后续更新