There are multiple approaches to solve this problem. The Python code for one approach I tried that does not use dynamic programming is shown below. To avoid repetition, the if statement checks that the number one lower than the current number is not present in the array before because then it could be included to increase the subsequence's length.

A = [3, 3, 4, 7, 5, 6, 8]

def longestConsecutive(nums):
    longest_streak = 0 #length of longest consecutive subsequence of integers
    indices = []
    
    for i in range(1,len(nums)):
        b = set(nums[0:i]) 
        if nums[i-1] - 1 not in b:
            indices.append(i) 
            current_num = nums[i-1]
            current_streak = 1
            k = i

            for j in range(k, len(nums)):  
                if A[j] == current_num   1:
                    indices.append(j 1) 
                    current_num  = 1
                    current_streak  = 1
                    k=j   

            if current_streak < longest_streak:
                indices = indices[0:len(indices)-current_streak]  #remove the current_streak's indices 
            else: 
                longest_streak = current_streak  
    
    return [longest_streak,indices[len(indices)-longest_streak:len(indices)]] 

c = longestConsecutive(A) 
print(c[0]) 
print(*c[1])

I think the time complexity for this algorithm is O(n) because the second for loop runs at most n times while the first for loop runs n-1 times and each lookup is O(1) because a set b is used. This is explained here in the solution to a different but related problem as my code is a modification of the third algorithm discussed. All other computations require constant time. Despite this, the algorithm passes tests 1-4 but fails test 5, for which the size of the input array is 200000 and the 2 second time limit is exceeded. Is the problem that the complexity is actually greater? Does anyone see how the code can be optimized?

CodePudding user response：

I feel like a recursive function is easier to understand and follow. Basically you want to only check if your current step is better than before, if not, move forward one. I am sure the sorted part could be made faster as well, as it is clearly not necessary to sort completely to conclude we have a non-inceasing sequence. I leave that to you to improve:

def f(x,n=1):
    if len(x)<n:
        return
    elif x[:n]==sorted(x[:n]):
        a = f(x,n 1) 
        return x[:n] if a is None else a
    return f(x[1:],n)

CodePudding user response：

Your algorithm has a O(