# Find the longest increasing subsequence of a list in C

I'm having problems trying to find the elements that form the Longest Increasing Subsequence of a given list.

I have the algorithm to find the value of a given item of the list, and I understand the method it uses, I just don't know what to add and where to add it so that I have the numbers that compose the L.I.S.

Here is what I'm doing now:

for (A[0] = N[0], i=lis=1; i<n; i++) { int *l = lower_bound(A, A+lis, N[i]); lis = max(lis, (l-A)+1); *l = N[i]; }

A is an array that stores the partial L.I.S., but at some point it changes because there may be a different solution. N is the array of elements.

How can I get from here to finding the longest increasing subsequence of N?

## Answers

You can use two additional array to find the LIS. For example, if your source is put in an array **A**

1 8 4 12 6 6 1

and we have an array **B** to store the elements of **A** which are more likely to be elements of LIS. More precisely, **B** will be maintained as an LIS at position **i**.
Plus an array **idx** to record the positions.

We begin from **A[0]**, place A[0] at B[0]. Since A[0] is appended at position 0 in **B**, idx[0] = 0.

[0] 1 2 3 4 5 6 A | 1 8 4 12 6 6 1 B | (1) idx | 0

Then for position 1, since element in **B** is smaller than A[1], A[1] is appended to B. idx[1] records the position in **B** which is 1.

0 [1] 2 3 4 5 6 A | 1 8 4 12 6 6 1 B | 1 (8) idx | 0 1

For position 2, A[2], or 4, is more likely to be an element of LIS compared to elements in **B** in order to maintain **B** as an LIS. So find the element in **B** which is the smallest one no less than 4 and replace, which is 8. idx[2] is set to the position where 8 is replaced in **B**. I think you can use your searching algorithm to find such an element.

0 1 [2] 3 4 5 6 A | 1 8 4 12 6 6 1 B | 1 (4) idx | 0 1 1

So continue this manner, we gradually set up **idx**.

position 3 0 1 2 [3] 4 5 6 A | 1 8 4 12 6 6 1 B | 1 4 (12) idx | 0 1 1 2 position 4 0 1 2 3 [4] 5 6 A | 1 8 4 12 6 6 1 B | 1 4 (6) idx | 0 1 1 2 2 position 5 0 1 2 3 4 [5] 6 A | 1 8 4 12 6 6 1 B | 1 4 (6) idx | 0 1 1 2 2 2 position 6 0 1 2 3 4 5 [6] A | 1 8 4 12 6 6 1 B | (1) 4 6 idx | 0 1 1 2 2 2 0

We have **idx** recorded positions, now we scan **idx** backwards and will find out the LIS.

0 1 2 3 4 5 6 A | 1 8 4 12 6 6 1 idx | 0 1 1 2 2 (2) 0 | 6 0 1 2 3 4 5 6 A | 1 8 4 12 6 6 1 idx | 0 1 (1) 2 2 2 0 | 4 6 0 1 2 3 4 5 6 A | 1 8 4 12 6 6 1 idx | (0) 1 1 2 2 2 0 | 1 4 6

Hence, the output LIS is {1, 4, 6}

The code and A = {1, 8, 4, 12, 6, 6, 1} as source

#include <stdio.h> #include <stdlib.h> #define INT_INF 10000 int search_replace(int *lis, int left, int right, int key) { int mid; for (mid = (left+right)/2; left <= right; mid = (left+right)/2) { if (lis[mid] > key) { right = mid - 1; } else if (lis[mid] == key) { return mid; } else if (mid+1 <= right && lis[mid+1] >= key) { lis[mid+1] = key; return mid+1; } else { left = mid + 1; } } if (mid == left) { lis[mid] = key; return mid; } lis[mid+1] = key; return mid+1; } int main(void) { int i, tmp, size = 7, lis_length = -1; int *answer; int A[7] = {1,8,4,12,6,6,1}, LIS[7], index[7] = {0}; LIS[0] = A[0]; for (i = 1; i < size; ++i) { LIS[i] = INT_INF; } for (i = 1; i < size; ++i) { index[i] = search_replace(LIS, 0, i, A[i]); if (lis_length < index[i]) { lis_length = index[i]; } } answer = (int*) malloc((lis_length+1) * sizeof(int)); for (i = size-1, tmp = lis_length; i >= 0; --i) { if (index[i] == tmp) { answer[tmp] = A[i]; --tmp; } } printf("LIS: "); for (i = 0; i < lis_length+1; ++i) { printf("%d ", answer[i]); } printf("\n"); return 0; }

And the output of the code

LIS: 1 4 6