# 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?

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 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) {
--tmp;
}
}

printf("LIS: ");
for (i = 0; i < lis_length+1; ++i) {
}
printf("\n");

return 0;
}
```

And the output of the code

```LIS: 1 4 6
```

### remove prevAll : first item with jQuery

What i`m doing wrong in my code:

### PHP “use” declarations repeated or with a comma?

I was curious to know, when declaring use statements with PHP at the start of a class, why the "use" keyword is generally repeated in each line even though it is