【分治】Leecode-53. 最大子数组和

【题目】

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

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

【题解】

题解1：

• 思路

     列出可能的树形图，对于给出的列表逐个遍历调用dfs

• 复杂度

         时间复杂度：O(n2)，空间复杂度：O(n)

• 代码

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