kjk81's garden

Longest Increasing Subsequence

2 min read

Brute Force 

for i in n
	for k in i
		if arr[k] < arr[i]:
			dp[i] = max(dp[k] + 1, dp[i])

each step, for every number that is less than the current, retain current subsequence length or add 1

solution

Utilize a vector where the size of the vector itself is the length of the length of the longest subsequence

Actual elements hold the minimum tail value for the length of a subseq at their index

Using this, if we iterate linearly from the start, we’re always computing integers later in the array after we compute first ones.

  • you know that the vector will be populated with values from earlier indices, so you can operate on the memo assuming that all values are all earlier

Because dp has minimum tail values in increasing order, where even if a different minimum tail is selected over the one in the longest increasing subsequence, it’s still smaller than , so we can perform b search or some logn algorithm to find the first value such that

Question

But why is adjusting the minimum tail value of the lower bound okay if the operation isn’t repeated for the elements above the lower bound

  • Actually doesn’t matter because we can update minimum tail no matter what for an element (actually, we want to, so we know the minimum value for a later value)
  • And if a lower bound isn’t found, then we know i is greater than all elements, and therefore have a longer length (so we append to vector arr)
  • These are both possible cases
  • We can track the

Stemming Question

Since by the end, we have a vector of the length of the LIS, could the entire vector actually be the LIS? No, can replace earlier indices with values reached at the end of iteration, which breaks what the actual sequence would be since it’s just minimum tails

Graph View