一、题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

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

示例1:

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

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

二、解题思路 & 代码

2.1 动态规划（改变原数组）

解题思路：

常见解法 时间复杂度 空间复杂度
暴力搜索 O ( N 2 ) O(N^2) O(N2) O ( 1 ) O(1) O(1)
分治思想 O ( N l o g N ) O(NlogN) O(NlogN) O ( l o g N ) O(logN) O(logN)
分治思想 O ( N ) O(N) O(N) O ( 1 ) O(1) O(1)

动态规划是本题的最优解法

空间复杂度降低：

由于 dp[i] 只与 dp[i−1] 和 nums[i] 有关系，因此可以将原数组 nums 用作 dp 列表，即直接在 nums 上修改即可。
由于省去dp 列表使用的额外空间，因此空间复杂度从 O(N) 降至 O(1) 。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)

复杂度分析：

  1. 时间复杂度O(N) ： 线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
  2. 空间复杂度 O(1) ： 使用常数大小的额外空间。

2.2 动态规划（不 改变原数组）

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max = nums[0]
        former = 0     #用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
        cur = nums[0]  #用于记录dp[i]的值
        for num in nums:
            cur = num;
            if(former>0):
                 cur +=former
            if(cur>max):
                 max = cur
            former=cur
        return max

复杂度分析：

  1. 时间复杂度O(N) ： 线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
  2. 空间复杂度 O(1) ： 使用常数大小的额外空间。

参考：LeetCode题解

==========================================================
详细注释：

""" No 53 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 """
from typing import List

class Solution:
    # def maxSubArray_1(self, nums: 'List[int]') -> 'int':
    def maxSubArray_1(self, nums):
        n = len(nums)
        max_sum = nums[0]
        for i in range(1, n):
            if nums[i - 1] > 0:
                nums[i] += nums[i - 1]
            max_sum = max(nums[i], max_sum)

        return max_sum

    # def maxSubArray_2(self, nums: 'List[int]') -> 'int':
    # def maxSubArray_2(self, nums):
    # """
    # 存在边界问题 错误
    # 输入：[-1]
    # 输出：0
    # 正确输出 ：-1
    # 
    # """
    # 
    # n = len(nums)
    # print("nums:",nums)
    # 
    # ThisSum = MaxSum = 0
    # for i in range(n):
    # ThisSum += nums[i] # 向右累加
    # print("i",i,"nums[i]",nums[i], "ThisSum:",ThisSum)
    # if (ThisSum > MaxSum):
    # MaxSum = ThisSum # 发现更大和则更新当前结果
    # elif (ThisSum < 0):
    # ThisSum = 0 # 若前面的子列和都已经小于零，那么不可能使得后面增大，所以抛弃
    # 
    # return MaxSum


if __name__ == '__main__':

    #nums = [-2,1,-3,4,-1,2,1,-5,4]

    nums = [1,1,1,1,1]

    solution = Solution()

    max_sum_1 = solution.maxSubArray_1(nums)
    max_sum_2 = solution.maxSubArray_2(nums)
    print(max_sum_1)
    print(max_sum_2)

""" 得到的结果是 5， 15 nums在执行第一个函数以后被更改了 """