leetcode最大子序和（python）
leetcode最大子序和（python）
題目
給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/maximum-subarray
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
解題思路
由題可知，需要找到一個最大和的連續子數組，並返回其最大和。既然是一個和，那麼我們就可以用兩個變數來表示：max_sum和current_sum，其中max_sum用來保存最終的值，而current_sum用來作比較的，就相當於一個。最開始，兩個變數都保存列表的第一個元素的值，然後通過遍曆元素，當我現在保存的和的值比現在元素的值小時，那麼就捨棄原來的保存的值，換成那個較大的元素的值，然後就比較我們保存的最終的值與現在的那個值，若我們保存最終的和小於現在的那個數的和，那麼就更新它的值。其中程式碼current_sum = max(current_time + num, num)的作用非常重要，首先current_sum + num表示求的是一個子列表的和，而num表示當前的元素，當前一個子列表的和小於改元素，我們就更新current_sum為num的值，然後開始下一個子列表。整個函數的最關鍵程式碼就是這一句。
程式碼
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
print('invalid array list')
return
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(current_sum + num, num)
max_sum = max(current_sum, max_sum)
return max_sum
Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
