I was solving the question of Longest Increasing Sub-sequence using dynamic programming with O(n^2) as per following pseudocode (Basically we are doing bottom-up approach to get length of largest increasing sub-sequence that ends at index i for 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
Though I got a different approach for O(nlog(n)) solution for above question, I thought of a modification in above approach that led me to another problem and I couldn't think of if I could solve that problem in better than O(n^2) time.
I thought that if I could know the largest element smaller than nums[i] for all i in [0, len(nums)-1] then I could do something like this (I am not sure if this approach is perfectly okay).
#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
Now, my question is not if above approach for the above mentioned problem is correct BUT that how to make the array left in less than O(n^2). If I could get left in less than O(n^2) the it will be worth to check if above approach works (though that's not the intention of asking this question here, I added that to show how I came across above problem). Can left be built in less than O(n^2). For clarity I am adding more input and output below for left (In below examples I will be showing required index in 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
