Continuous Subarray Sum

Question

Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

Analysis

跟 maximum array其实一样，只不过这里要return的不是maximum sum的value, 而是区间的index

Thoughts

依然dp, 更新start和end两个value,当找到一个暂时的maximum sum时，记录下来

Solution

class Solution:
    # @param {int[]} A an integer array
    # @return {int[]}  A list of integers includes the index of the 
    #                  first number and the index of the last number
    def continuousSubarraySum(self, A):
        # Write your code here
        if not A:
            return 0
        currentSum = 0
        length = len(A)
        maxSum = sys.maxint * -1
        maxStart = 0
        maxEnd = 0
        start = 0
        for i in range(length):
            if currentSum < 0:
                currentSum = A[i]
                start = i
            else:
                currentSum += A[i]
            if maxSum < currentSum:
                maxSum = currentSum
                maxStart = start
                maxEnd = i

        return [maxStart, maxEnd]