LeetCode 53 最大子序和 牛客題霸 子數組的最大累加和問題

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

解題思路：

動态規劃。狀态轉移方程：f(i)=max{f(i−1)+ai​,ai​}

Python代碼：

#
# max sum of the subarray
# @param arr int整型一維數組 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        res = m = float('-inf')
        for x in arr:
            m = max(m+x, x)
            res = max(m, res)
        return res