Help! Time Limit Exceeded for the array [[10000,9999,9998,9997,9996,....]


  • 0
    U

    My code as following, but after test, it said "Time Limit Exceeded for the array [[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976....]", but I have already added the "decrease" scenario in the beginning of the code, which will only scan array for once will get the answer "0", but still said the Time Limit Exceeded, what's the issue here ?

    class Solution:
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
            length = len(prices)
            if length == 1 or length == 0:
                return 0
    
            decrease = True
            for i in xrange(length-1):
                if prices[i+1] > prices[i]:
                    decrease = False
            if decrease:
                return 0
    
            i = 0
            min_index = 0
            max_index = 0
            result = 0
            temp_result = 0
            first_result = 0
            second_result = 0
            pre_min_index = 0
            pre_max_index = 0
    
            while i < length:
                while (prices[i] > prices[max_index]) and i < length:
                    max_index = i
                    if (temp_result < prices[max_index] - prices[min_index]):
                            temp_result = prices[max_index] - prices[min_index]
                    if i < length -1:
                        i += 1
    
                if max_index != pre_max_index:
                    temp_result2 = prices[max_index] - prices[pre_min_index]
                    if temp_result < temp_result2:
                        first_result = temp_result2
                        second_result = 0
                        pre_min_index = i
                    else:
                        if first_result < temp_result :
                            second_result = first_result
                            first_result = temp_result
                        elif second_result < temp_result:
                            second_result = temp_result
                    temp_result = 0
                    if i != length -1:
                        pre_max_index = min_index = max_index = i
    
                if prices[i] < prices[min_index]:
                    min_index = i
                    if min_index > max_index:
                        max_index = min_index
                        pre_max_index = min_index
                    if prices[min_index] < prices[pre_min_index]:
                        pre_min_index = min_index
                    if first_result < temp_result :
                        second_result = first_result
                        first_result = temp_result
                    elif second_result < temp_result:
                        second_result = temp_result
                    temp_result = 0
    
                i += 1
    
            if max_index < min_index:
                return 0
    
            return first_result + second_result

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 2
    H

    How do you know the input is monotonically decreasing? The complete input list is not shown anyway.
    You should work on a general solution to this problem that can automatically take care of all possible input.


  • 0
    S

    It's because that sequence is not mono-decreasing.


Log in to reply
 

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