Accepted fast Python code based on "stock selling problem"


  • 0
    L

    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[0],A[0]
            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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.