Я решал вопрос Самая длинная возрастающая подпоследовательность , используя динамическое программирование с O(n^2) согласно следующему псевдокоду (в основном мы делаем восходящий подход, чтобы получить длину наибольшей увеличивающейся подпоследовательности, котораяоканчивается на индекс i для all i of given array):
#nums is sequence of numbers like [10,9,2,5,3,7,101,18]
dp=[1]*len(nums) #dp[i] is length of longest increasing sub-sequence ending at element nums[i]
for i in range(len(lst)):
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i], dp[j]+)
#max(dp) will give the length of Longest Increasing Sub-sequence
Хотя у меня есть другой подход для O(nlog(n)) решения для вышеуказанного вопроса, я подумал о модификации в вышеуказанном подходеэто привело меня к другой проблеме, и я не мог придумать, смогу ли я решить эту проблему быстрее, чем за O(n^2) время.
Я думал, что если бы я мог знать самый большой элемент, меньший чем nums[i] для all i in [0, len(nums)-1] тогда я мог бы сделать что-то подобное (я не уверен, что этот подход вполне подходит).
#nums is sequence of numbers like [10,9,2,5,3,7,101,18]
left=[]
#Suppose left is a list of length len(nums) such that left[i] will give largest element smaller than nums[i] in left sub-array for nums (excluding i)
#i.e. for above nums array, left = [-1,-1,-1,2,2,5,10,10] #I am showing values here for clarity but I can as well store index of largest element smaller than nums[i] for quick access
#No element is left to 10 so left[0]=-1
#No element left to 9 is smaller than 9 so left[1]=-1
#No element left to 2 is smaller than 2 so left[2]=-1
#In array left to 5, 2 is than largest element smaller than 5 so, left[3]=2, and so on
#Now
dp=[1]*len(lst) #dp[i] is length of longest increasing sub-sequence ending at element nums[i]
for i in range(len(lst)):
if left[i]!=-1:
dp[i]=max(dp[i], dp[left[i]]+1) #Assuming I am storing indices in array left
Теперь , мой вопрос не в том, подходит ли вышеуказанный подход для вышеупомянутогопроблема правильная НО в том, как сделать массив left меньше O(n^2). Если бы я мог получить left меньше чем O(n^2), то стоило бы проверить, работает ли вышеуказанный подход (хотя это и не было целью задать этот вопрос здесь, я добавил это, чтобы показать, как я столкнулся с вышеуказанной проблемой). Может ли left быть построен менее чем O(n^2). Для ясности я добавляю дополнительные входные и выходные данные для left (в приведенных ниже примерах я буду показывать требуемый индекс в left):
Input: [10,9,2,5,3,7,101,18]
Output: [-1,-1,-1,2,2,3,0,0]
Input: [10,9,8,7,6,8]
Output: [-1,-1,-1,-1,-1,3] #largest element smaller than 8 in left sub-array of 8 is 7 whose index is 3
Input: [0,1,2,3,4,5,6]
Output: [-1,0,1,2,3,4,5] #no element in left sub-array of element 0, so left[0]=-1