Maximum Subarray - LeetCode

Maximum Subarray - LeetCode
タイトル:
Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array  [−2,1,−3,4,−1,2,1,−5,4] , the contiguous subarray  [4,−1,2,1]  has the largest sum =  6 . 分析:
これは動的計画のテーマです.私は他人の考えを参考にしているので、ここで彼の考えを話します.
基本的な考え方はこのようにして、各ステップで、私たちは2つの変数を維持して、1つはグローバルで最も優れていて、現在の要素まで最も優れている解は、1つは局所的に最も優れていて、現在の要素を含まなければならない最も優れている解です.次にダイナミックプランニングの繰返し式についてお話しします(これはダイナミックプランニングの最も重要なステップであり、再帰式が出てきて、基本的にコードフレームワークも出てきます).iステップ目のglobal[i](グローバル最適化)とlocal[i](ローカル最適化)が知られていると仮定すると、i+1ステップ目の式は、
local[i+1]=Math.max(A[i],local[i]+A[i])は、局所最適化は必ず現在の要素を含むので、そうでなければ前のステップの局所最適local[i]+現在の要素A[i](local[i]は必ずi番目の要素を含むので、条件に違反しません)ですが、local[i]が負であれば、彼を加えるより不要なので、そうでなければ直接A[i]を使います.global[i+1]=Math(local[i+1],global[i])は、現在のステップのローカル最適化があり、グローバル最適化は、現在のローカル最適化または元のグローバル最適化である(最適解が現在の要素を含まない場合、前はグローバル最適化の中に維持され、現在の要素が含まれている場合、このローカル最適化であるため、すべての状況がカバーされる).
コード:

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        lmax,gmax = A[0],A[0]
        for  i in xrange(1,len(A)):
            lmax = max(lmax+A[i],A[i])
            gmax= max(lmax,gmax)
        return gmax