Leetcode-Maximum Subarray-Python
Maximum Subarray
最大サブストリングと問題:1つの配列からサブストリングを見つけて最大にします.Description
tips:サブストリングは指数群で連続するいくつかの要素であり、サブシーケンスは各要素の順序が配列で一致することを要求し、連続的な要求はない.
解題の構想:自分で考えていないで、直接ネット上の動態の計画の構想を参考にして、私は以下がいくつかの解決の肝心な点だと思います:-array[1...n]に対して、もしarray[i...j]が満足して最大の子列であれば、それではいかなるk(i<=k<=j)に対して、私達はarray[i...k]のと0より大きいことがあります.アテステーション-0が既知であると仮定し、..kの最大とsum[k]以降では、0,…,k+1の最大とsum[k+1]は、sum[k]>=0の場合、sum[k+1]=sum[k]+A[k+1]の2つに分けられる.コードにはcurSum=curSum+nums[i]があります.2)sum[k]<0の場合、sum[k+1]=A[k+1]となるようにSubArrayをもう1つ付けます.コードはcurSum=nums[i].
最大サブストリングと問題:1つの配列からサブストリングを見つけて最大にします.Description
tips:サブストリングは指数群で連続するいくつかの要素であり、サブシーケンスは各要素の順序が配列で一致することを要求し、連続的な要求はない.
解題の構想:自分で考えていないで、直接ネット上の動態の計画の構想を参考にして、私は以下がいくつかの解決の肝心な点だと思います:-array[1...n]に対して、もしarray[i...j]が満足して最大の子列であれば、それではいかなるk(i<=k<=j)に対して、私達はarray[i...k]のと0より大きいことがあります.アテステーション-0が既知であると仮定し、..kの最大とsum[k]以降では、0,…,k+1の最大とsum[k+1]は、sum[k]>=0の場合、sum[k+1]=sum[k]+A[k+1]の2つに分けられる.コードにはcurSum=curSum+nums[i]があります.2)sum[k]<0の場合、sum[k+1]=A[k+1]となるようにSubArrayをもう1つ付けます.コードはcurSum=nums[i].
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
curSum = maxSum = nums[0]
for i in range(1, len(nums)):
curSum = max(nums[i], curSum+nums[i])
maxSum = max(maxSum, curSum)
return maxSum