剣指offer(python)動的計画——55.連続サブ配列の最大和

55.(簡単)——動的計画
空でない配列を入力します.配列の数は正でも負でもあります.
配列内の1つまたは複数の整数がサブ配列を構成します.
すべてのサブ配列の和の最大値を求めます.
要求時間複雑度はO(n)である.
サンプル

  ：[1, -2, 3, 10, -4, 7, 2, -5]

  ：18

問題解決の考え方:
どうてきけいかくもんだい
状態:dp[i]現在iで終わる連続配列の最大値を記録する
(1)dp[i]=dp[i-1]+nums[i]がnum[i]より小さい場合は、dp[i]は連続配列の最大値ではなく、別のかまど、dp[i]=nums[i]であり、状態を[i]から再開し、この状態を記録する
(2)dp[i]=dp[i-1]+nums[i]がnum[i]より小さい場合はdp[i]が連続配列の最大値となり、この状態を記録する
(3)配列が空である場合や1である場合など,特殊な状況を考える.
参照コード:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        size = len(nums)
        dp = [False for _ in range(size)]#    ：   i           
        if size==0 :#  1
            return None
        if size==1: #  2
            return nums[0]
        dp[0] =nums[0] 
        #    
        for i in range(1,size):
            dp[i] = max(dp[i-1]+nums[i],nums[i])#      
        return max(dp)