-
Notifications
You must be signed in to change notification settings - Fork 233
/
longest-increasing-subsequence.py
57 lines (48 loc) · 1.62 KB
/
longest-increasing-subsequence.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# LONGEST INCREASING SUBSEQUENCE
# O(N^2) time and O(N) space
def longestIncreasingSubsequence(array):
# Write your code here.
lengths = [1 for _ in array]
sequences = [None for _ in array]
start, maxLength = 0, 0
for idx in range(len(lengths)):
for prev in range(idx):
if array[prev] < array[idx] and lengths[prev] + 1 > lengths[idx]:
lengths[idx] = lengths[prev] + 1
sequences[idx] = prev
if lengths[idx] > maxLength:
maxLength = lengths[idx]
start = idx
return buildSequence(array, sequences, start)
def buildSequence(array, sequences, start):
result = [array[start]]
while sequences[start] != None:
result.append(array[sequences[start]])
start = sequences[start]
return list(reversed(result))
# O(NlogN) time and O(N) space
def longestIncreasingSubsequence(array):
sequences = [None for x in array]
indices = [None for x in range(len(array) + 1)]
length = 0
for i, num in enumerate(array):
newLength = binarySearch(1, length, indices, array, num)
sequences[i] = indices[newLength - 1]
indices[newLength] = i
length = max(length, newLength)
return buildSequence(array, sequences, indices[length])
def binarySearch(startIdx, endIdx, indices, array, num):
if startIdx > endIdx:
return startIdx
middleIdx = (startIdx + endIdx) // 2
if array[indices[middleIdx]] < num:
startIdx = middleIdx + 1
else:
endIdx = middleIdx - 1
return binarySearch(startIdx, endIdx, indices, array, num)
def buildSequence(array, sequences, start):
result = [array[start]]
while sequences[start] != None:
result.append(array[sequences[start]])
start = sequences[start]
return list(reversed(result))