Combinations (Python)

Largest Rectangle in Histogram (Python)

Maximum Subarray (Python)

kitt posted @ 2014年1月31日 21:50 in LeetCode , 1871 阅读

看了Discuss才会的, 题目说还可以divide and conquer, 咋整捏? S[i]存的是以A[i]为结尾的Subarray的最大和。

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

评论 (0)