-1

I wrote a code to obtain non decreasing sub-sequence from a python list

lis = [3, 6, 3, 8, 6, 4, 2, 9, 5]
ind = 0
newlis = []
while ind < len(lis):
    minele = min(lis[ind:])
    newlis.append(minele)
    ind = lis.index(minele) + 1
print(newlis)

Though it seems to be working fine with the testcases I tried, is there a more efficient way to do this, because the worst cast time complexity of this code is O(n^2) for the case the list is already sorted, assuming the built-in min method uses linear search.

To be more precise, I want longest possible non decreasing sub-list and the sub-list should start with the minimum element of the list. And by sub-list, I mean that the elements need not be in a contiguous stretch in the given original list (lis).

virmis_007
  • 173
  • 1
  • 4
  • 17
  • 1
    Your code outputs `[2, 5]`, the last occurring non-decreasing subsequence. Can you explain which non-decreasing subsequence should be the output? Do you want the longest one, or all of them, or will any of them do? The [longest subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) can be found in O(n log n) time. – Alex Riley Mar 02 '19 at 10:49
  • `[2,5]` as outputted does not exist in your list. – Patrick Artner Mar 02 '19 at 10:50
  • this code seem to be just jumping to the next smallest element in remaining list and adding it to the list. so what do you mean by subsequence exactly – Jarek.D Mar 02 '19 at 10:51
  • I assume OP means non-contiguous subsequence, looking at their code. – Alex Riley Mar 02 '19 at 10:52
  • @Jarek.D edited the question – virmis_007 Mar 02 '19 at 10:56
  • (reply to edit) the longest non-decreasing subsequence is of length 3 - `[3, 4, 5]` or `[3, 4, 9]` (there are others too) so it seems there's a mistake in your code snippet. – Alex Riley Mar 02 '19 at 10:56
  • @AlexRiley It should start with minimum element – virmis_007 Mar 02 '19 at 10:58
  • @virmis_007: oh I see - in that case your code has the correct output, but the problem is still solvable in O(n log n) time via the Wikipedia link. – Alex Riley Mar 02 '19 at 10:59
  • well if sequence must start from the min element then there is only a single sequence that you are looking for and you should find the min before while loop and then do a linear scan to append non decreasing elements and that will run in O(n) time – Jarek.D Mar 02 '19 at 11:07
  • @Jarek.D - that's not correct - there can be multiple longest non-decreasing subsequences. It is not solvable in linear time, because you will have to scan the whole list N times with your method, where N is the number of items after the minimum element. – Alex Riley Mar 02 '19 at 11:11
  • @AlexRiley I really struggle to see how? If the subsequence must start from min and if it doesn't need to be contiguous then the longest sequence will be always the one starting from min element – Jarek.D Mar 02 '19 at 11:35
  • @Jarek.D: for example in `[9, 1, 3, 8, 9, 6, 9, 8, 2, 3, 4, 5]`, if you scan as you suggest, you'll end up with the sequence `[1, 3, 8, 9]`, but the longest is actually `[1, 2, 3, 4, 5]`. You have to do a liner scan over the remaining elements for each possible next starting element of the subsequence. This is quadratic - it is essentially what OP's code is doing. – Alex Riley Mar 02 '19 at 11:47
  • @AlexRiley still not convinced by your example list. I'd just need to keep trying to build a longer sequence during a single scan. Coded the answer below – Jarek.D Mar 02 '19 at 12:06

1 Answers1

0

I'm almost convinced it can run in linear time. You just need to keep trying to build a longest sequence during one scan and either store them all as I did or keep currently longest one.

lis = [9, 1, 3, 8, 9, 6, 9, 8, 2, 3, 4, 5]
newlis = [[]]
minele = min(lis)
ind = lis.index(minele)
currmin = minele
seq = 0
longest = 0
longest_idx = None
while ind < len(lis):
    if lis[ind] >= currmin:
        newlis[seq].append(lis[ind])
        currmin = lis[ind]
        ind += 1
    else:
        if len(newlis[seq]) > longest:
            longest = len(newlis[seq])
            longest_idx = seq
        newlis.append([minele])
        currmin = minele
        seq += 1

if len(newlis[seq]) > longest:
    longest = len(newlis[seq])
    longest_idx = seq

print(newlis)
print(newlis[longest_idx])
Jarek.D
  • 1,274
  • 1
  • 8
  • 18
  • Try with `lis = [6, 0, 8, 1, 3, 6, 2, 5, 9, 4, 8]`. A longest subsequence should be `[0, 1, 3, 5, 8]`, but the code finds only subsequences of length 4 and fewer. Can this be fixed? I still think a general solution requires O(n log n) time. – Alex Riley Mar 02 '19 at 12:28
  • Right that is a problem. But maybe it could be fixed at some cost of memory complexity. I could store all possible gathered subsequences separately (so eg [0,1], [0,1,3]) and then after the sequence breaks try to concatenate the new local minimum to the longest previous subsequence, that has maximum value lower or equal than current new minimum. Just an idea, not sure how optimal for large sequences but in principle it should be still a singe scan with some additional time proportional to the number of currently gathered subseqences. So not really O(n) but possibly better than O(n logn) – Jarek.D Mar 02 '19 at 13:29
  • I appreciate everyone's time and efforts. I think I've failed at explaining what exactly what I wanted. Cannot give more context to the problem (which could've perhaps added more clarity) I am aiming to solve due to certain reasons. – virmis_007 Mar 02 '19 at 13:39