Maximum Subarray[LeetCode/Python3/Medium]

 

題目

給定一個整數數組 nums，找到具有最大和的子數組並返回其和。

示例 1:

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 數組中具有最大和的子數組為 [4,-1,2,1]，其和為 6。

示例 2:

輸入: nums = [1]
輸出: 1
解釋: 數組中具有最大和的子數組為 [1]，其和為 1。

示例 3:

輸入: nums = [5,4,-1,7,8]
輸出: 23
解釋: 數組中具有最大和的子數組為 [5,4,-1,7,8]，其和為 23。

限制:

• 1 <= nums.length <= 105
• 104 <= nums[i] <= 104

進階: 如果你已經實現了$ O(n) $的解法，嘗試使用更為複雜的分治策略求解。

我的答案

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

我的時間複雜度好爛喔ＱＱ

找時間再來思考有沒有比較好的方法