今天是紀錄LeetCode解題的第五十三天

第五十三題題目：Given an integer array nums, find the subarray with the largest sum, and return its sum.

給定一個整數數組nums，找出總和最大的子陣列，並回傳它的總和值

解題思路

這題的經典解法是Kadane's Algorithm，是一種用於解決最大子數組的動態規劃算法，我們要找到某一段連續區間，使得他的總和最大，首先我們要判斷當前數字nums[i]值不值得被放進子陣列當中，所以要比較curr_sum = max(nums[i],curr_sum + nums[i])，如果nums[i]比較大，表示nums[i]加到子陣列當中並沒有比較好(因為前面總和可能為負)，那重新把nums[i]變成開頭開始找新的子陣列，那如果curr_sum + nums[i]比較大，那麼我們把nums[i]加入到子陣列當中繼續延伸此子陣列，接著比較max_sum = max(max_sum , curr_sum)，紀錄更新最大子陣列總和

程式碼

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = max_sum = nums[0]
        for i in range(1,len(nums)):
            curr_sum = max(nums[i],curr_sum + nums[i])#比較當前值和把當前值加前面總和誰大，如果當前值大，就重新當開頭，
            max_sum = max(max_sum , curr_sum)         #如果加到前面比較大，那麼把當前值加入繼續延伸該子陣列
        return max_sum

執行過程

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