The code is based on the best time buy and selling stock, with slight changes. Its time complexity is O(n). The running time for the test is around 100ms. Any comments would be appreciated.
class Solution: # @param A, a list of integers # @return an integer def maxSubArray(self, A): # can transfer to the sell stock problem. # front, end are buying and selling dates. maxVal would be the profit front,end,maxVal=0,A,A for ii in range(1,len(A)): # transfer the array. The new array contains the summary from the first element to current element A[ii]+=A[ii-1] if A[ii]>end: maxVal,end=max(maxVal,A[ii]-front),A[ii] #A[ii-1] instead, because the problem ask for trading with minimum interval of one day. if A[ii-1]<front: front,end,maxVal=A[ii-1],A[ii],max(maxVal,A[ii]-A[ii-1]) return maxVal