Количество всех самых длинных возрастающих подпоследовательностей
Я практикую алгоритмы, и одна из моих задач - подсчитать количество всех самых длинных увеличивающихся подпоследовательностей для заданных 0
Я уже реализовал поиск LIS и его длины ( алгоритм LIS), но этот алгоритм переключает числа на минимально возможное значение. Следовательно, невозможно определить, смогут ли подпоследовательности с предыдущим числом (большим) достичь наибольшей длины, иначе я мог бы просто посчитать эти переключатели, я полагаю.
Любые идеи, как получить это о O (nlogn)? Я знаю, что это нужно решать с помощью динамического программирования.
Я реализовал одно решение, и оно работает хорошо, но оно требует двух вложенных циклов (i в 1..n) x (j в 1..i-1).
Так что это O(n^2), я думаю, тем не менее, это слишком медленно.
Я даже пытался переместить эти числа из массива в двоичное дерево (потому что в каждой итерации я ищу все меньшие числа, чем число [i] - проходя через элементы i-1..1), но это было еще медленнее.
Пример тестов:
1 3 2 2 4
result: 3 (1,3,4 | 1,2,4 | 1,2,4)
3 2 1
result: 3 (1 | 2 | 3)
16 5 8 6 1 10 5 2 15 3 2 4 1
result: 3 (5,8,10,15 | 5,6,10,15 | 1,2,3,4)
4 ответа
Нахождение количества всех самых длинных увеличивающихся подпоследовательностей
Полный Java-код улучшенного алгоритма LIS, который обнаруживает не только длину самой длинной увеличивающейся подпоследовательности, но и количество подпоследовательностей такой длины, приведен ниже. Я предпочитаю использовать дженерики, чтобы разрешить не только целые числа, но и любые сопоставимые типы.
@Test
public void testLisNumberAndLength() {
List<Integer> input = Arrays.asList(16, 5, 8, 6, 1, 10, 5, 2, 15, 3, 2, 4, 1);
int[] result = lisNumberAndlength(input);
System.out.println(String.format(
"This sequence has %s longest increasing subsequenses of length %s",
result[0], result[1]
));
}
/**
* Body of improved LIS algorithm
*/
public <T extends Comparable<T>> int[] lisNumberAndLength(List<T> input) {
if (input.size() == 0)
return new int[] {0, 0};
List<List<Sub<T>>> subs = new ArrayList<>();
List<Sub<T>> tails = new ArrayList<>();
for (T e : input) {
int pos = search(tails, new Sub<>(e, 0), false); // row for a new sub to be placed
int sum = 1;
if (pos > 0) {
List<Sub<T>> pRow = subs.get(pos - 1); // previous row
int index = search(pRow, new Sub<T>(e, 0), true); // index of most left element that <= e
if (pRow.get(index).value.compareTo(e) < 0) {
index--;
}
sum = pRow.get(pRow.size() - 1).sum; // sum of tail element in previous row
if (index >= 0) {
sum -= pRow.get(index).sum;
}
}
if (pos >= subs.size()) { // add a new row
List<Sub<T>> row = new ArrayList<>();
row.add(new Sub<>(e, sum));
subs.add(row);
tails.add(new Sub<>(e, 0));
} else { // add sub to existing row
List<Sub<T>> row = subs.get(pos);
Sub<T> tail = row.get(row.size() - 1);
if (tail.value.equals(e)) {
tail.sum += sum;
} else {
row.add(new Sub<>(e, tail.sum + sum));
tails.set(pos, new Sub<>(e, 0));
}
}
}
List<Sub<T>> lastRow = subs.get(subs.size() - 1);
Sub<T> last = lastRow.get(lastRow.size() - 1);
return new int[]{last.sum, subs.size()};
}
/**
* Implementation of binary search in a sorted list
*/
public <T> int search(List<? extends Comparable<T>> a, T v, boolean reversed) {
if (a.size() == 0)
return 0;
int sign = reversed ? -1 : 1;
int right = a.size() - 1;
Comparable<T> vRight = a.get(right);
if (vRight.compareTo(v) * sign < 0)
return right + 1;
int left = 0;
int pos = 0;
Comparable<T> vPos;
Comparable<T> vLeft = a.get(left);
for(;;) {
if (right - left <= 1) {
if (vRight.compareTo(v) * sign >= 0 && vLeft.compareTo(v) * sign < 0)
return right;
else
return left;
}
pos = (left + right) >>> 1;
vPos = a.get(pos);
if (vPos.equals(v)) {
return pos;
} else if (vPos.compareTo(v) * sign > 0) {
right = pos;
vRight = vPos;
} else {
left = pos;
vLeft = vPos;
}
}
}
/**
* Class for 'sub' pairs
*/
public static class Sub<T extends Comparable<T>> implements Comparable<Sub<T>> {
T value;
int sum;
public Sub(T value, int sum) {
this.value = value;
this.sum = sum;
}
@Override public String toString() {
return String.format("(%s, %s)", value, sum);
}
@Override public int compareTo(Sub<T> another) {
return this.value.compareTo(another.value);
}
}
объяснение
Поскольку мое объяснение кажется длинным, я назову исходную последовательность "seq", а любую ее подпоследовательность - "sub". Таким образом, задача состоит в том, чтобы вычислить количество самых длинных увеличивающихся подпрограмм, которые можно получить из последовательности.
Как я упоминал ранее, идея состоит в том, чтобы вести подсчет всех возможных самых длинных сабвуферов, полученных на предыдущих этапах. Итак, давайте создадим нумерованный список строк, где номер каждой строки равен длине подпрограмм, хранящихся в этой строке. И давайте сохраним подпрограммы как пары чисел (v, c), где "v" - это "значение" конечного элемента, "c" - это "количество" подпрограмм данной длины, которые заканчиваются на "v". Например:
1: (16, 1) // that means that so far we have 1 sub of length 1 which ends by 16.
Построим такой список шаг за шагом, взяв элементы из начальной последовательности по их порядку. На каждом шаге мы будем пытаться добавить этот элемент к самой длинной подпрограмме, к которой он может быть добавлен, и записывать изменения.
Составление списка
Давайте построим список, используя последовательность из вашего примера, так как он имеет все возможные варианты:
16 5 8 6 1 10 5 2 15 3 2 4 1
Сначала возьмем элемент 16. Наш список пока пуст, поэтому мы просто добавили в него одну пару:
1: (16, 1) <= one sub that ends by 16
Далее 5. Его нельзя добавить к сабвуферу, который заканчивается на 16, поэтому он создаст новый саб с длиной 1. Мы создадим пару (5, 1) и поместим ее в строку 1:
1: (16, 1)(5, 1)
Элемент 8 будет следующим. Он не может создать подпункт [16, 8] длины 2, но может создать подпункт [5, 8]. Итак, вот где идет алгоритм. Сначала мы перебираем строки списка вверх ногами, рассматривая "значения" последней пары. Если наш элемент больше, чем значения всех последних элементов во всех строках, мы можем добавить его к существующим подпунктам, увеличив его длину на единицу. Таким образом, значение 8 создаст новую строку списка, потому что оно больше, чем значения всех последних элементов, существующих в списке на данный момент (т. Е. > 5):
1: (16, 1)(5, 1)
2: (8, ?) <=== need to resolve how many longest subs ending by 8 can be obtained
Элемент 8 может продолжаться 5, но не может продолжаться 16. Поэтому нам нужно выполнить поиск по предыдущей строке, начиная с ее конца, вычисляя сумму "подсчетов" в парах, "значение" которых меньше 8:
(16, 1)(5, 1)^ // sum = 0
(16, 1)^(5, 1) // sum = 1
^(16, 1)(5, 1) // value 16 >= 8: stop. count = sum = 1, so write 1 in pair next to 8
1: (16, 1)(5, 1)
2: (8, 1) <=== so far we have 1 sub of length 2 which ends by 8.
Почему мы не храним значение 8 в подпрограммах длины 1 (первая строка)? Потому что нам нужны сабы максимально возможной длины, а 8 могут продолжить некоторые предыдущие сабы. Таким образом, каждое последующее число, большее 8, также продолжит такую подпункт, и нет необходимости сохранять 8 как подпоследовательность меньшей, чем это может быть.
Следующий. 6 Поиск вверх ногами по последним "значениям" в строках:
1: (16, 1)(5, 1) <=== 5 < 6, go next
2: (8, 1)
1: (16, 1)(5, 1)
2: (8, 1 ) <=== 8 >= 6, so 6 should be put here
Найдена комната на 6, нужно посчитать количество:
take previous line
(16, 1)(5, 1)^ // sum = 0
(16, 1)^(5, 1) // 5 < 6: sum = 1
^(16, 1)(5, 1) // 16 >= 6: stop, write count = sum = 1
1: (16, 1)(5, 1)
2: (8, 1)(6, 1)
После обработки 1:
1: (16, 1)(5, 1)(1, 1) <===
2: (8, 1)(6, 1)
После обработки 10:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)
3: (10, 2) <=== count is 2 because both "values" 8 and 6 from previous row are less than 10, so we summarized their "counts": 1 + 1
После обработки 5:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1) <===
3: (10, 2)
После обработки 2:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1) <===
3: (10, 2)
После обработки 15:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)
4: (15, 2) <===
После обработки 3:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)(3, 1) <===
4: (15, 2)
После обработки 2:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2) <===
3: (10, 2)(3, 1)
4: (15, 2)
Если при поиске строк по последнему элементу мы находим равный элемент, мы снова вычисляем его "количество" на основе предыдущей строки и добавляем к существующему "числу".
После обработки 4:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2)
3: (10, 2)(3, 1)
4: (15, 2)(4, 1) <===
После обработки 1:
1: (16, 1)(5, 1)(1, 2) <===
2: (8, 1)(6, 1)(5, 1)(2, 2)
3: (10, 2)(3, 1)
4: (15, 2)(4, 1)
Итак, что мы имеем после обработки всей начальной последовательности? Глядя на последний ряд, мы видим, что у нас есть 3 самых длинных сабвуфера, каждый из которых состоит из 4 элементов: 2 заканчиваются на 15 и 1 заканчиваются на 4.
А как насчет сложности?
На каждой итерации, беря следующий элемент из исходной последовательности, мы делаем 2 цикла: первый при итерации строк, чтобы найти место для следующего элемента, и второй при суммировании счетчиков в предыдущей строке. Таким образом, для каждого элемента мы делаем максимум от n итераций (в худшем случае: если начальный seq состоит из элементов в порядке возрастания, мы получим список из n строк с 1 парой в каждой строке; если seq отсортирован в порядке убывания, мы получим список из 1 строки с n элементами). Кстати, сложность O (n 2) - это не то, что нам нужно.
Во-первых, это очевидно, что в каждом промежуточном состоянии строки сортируются по возрастанию их последнего "значения". Таким образом, вместо грубой петли можно выполнить бинарный поиск, сложность которого равна O(log n).
Во-вторых, нам не нужно суммировать "числа" подпрограмм, каждый раз просматривая элементы строки. Мы можем суммировать их в процессе, когда новая пара добавляется в строку, например:
1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row
Таким образом, второе число будет показывать не количество самых длинных подпрограмм, которые могут быть получены с заданным значением в конце, а суммарное количество всех самых длинных подпрограмм, которые заканчиваются любым элементом, который больше или равен "значению" из пары.
Таким образом, "подсчеты" будут заменены "суммами". И вместо итерации элементов в предыдущей строке мы просто выполняем бинарный поиск (это возможно, потому что пары в любой строке всегда упорядочены по их "значениям") и принимаем "сумму" для новой пары как "сумму" последнего элемента в предыдущей строке минус "сумма" от элемента слева до найденной позиции в предыдущей строке плюс "сумма" предыдущего элемента в текущей строке.
Итак, при обработке 4:
1: (16, 1)(5, 2)(1, 3)
2: (8, 1)(6, 2)(5, 3)(2, 5)
3: (10, 2)(3, 3)
4: (15, 2) <=== room for (4, ?)
search in row 3 by "values" < 4:
3: (10, 2)^(3, 3)
4 будет связан с (3-2+2): ("сумма" из последней пары предыдущей строки) - ("сумма" от пары слева до найденной позиции в предыдущей строке) + ("сумма" из предыдущей пары в текущем строка):
4: (15, 2)(4, 3)
В этом случае окончательный счет всех самых длинных подпрограмм равен "сумме" из последней пары последней строки списка, то есть 3, а не 3 + 2.
Таким образом, выполняя бинарный поиск как для поиска строк, так и для поиска по сумме, мы получим O(n*log n) сложность.
Что касается потребляемой памяти, то после обработки всего массива мы получим максимум n пар, поэтому потребление памяти в случае динамических массивов будет O(n). Кроме того, при использовании динамических массивов или коллекций требуется дополнительное время для их выделения и изменения размера, но большинство операций выполняется за время O(1), потому что мы не выполняем сортировку и перегруппировку во время процесса. Таким образом, оценка сложности представляется окончательной.
Cpp реализация вышеуказанной логики:
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pob pop_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ll long long
#define ull unsigned long long
#define fori(a,b) for(i=a;i<b;i++)
#define forj(a,b) for(j=a;j<b;j++)
#define fork(a,b) for(k=a;k<b;k++)
#define forl(a,b) for(l=a;l<b;l++)
#define forir(a,b) for(i=a;i>=b;i--)
#define forjr(a,b) for(j=a;j>=b;j--)
#define mod 1000000007
#define boost std::ios::sync_with_stdio(false)
struct comp_pair_int_rev
{
bool operator()(const pair<int,int> &a, const int & b)
{
return (a.first > b);
}
bool operator()(const int & a,const pair<int,int> &b)
{
return (a > b.first);
}
};
struct comp_pair_int
{
bool operator()(const pair<int,int> &a, const int & b)
{
return (a.first < b);
}
bool operator()(const int & a,const pair<int,int> &b)
{
return (a < b.first);
}
};
int main()
{
int n,i,mx=0,p,q,r,t;
cin>>n;
int a[n];
vector<vector<pii > > v(100005);
vector<pii > v1(100005);
fori(0,n)
cin>>a[i];
v[1].pb({a[0], 1} );
v1[1]= {a[0], 1};
mx=1;
fori(1,n)
{
if(a[i]<=v1[1].first)
{
r=v1[1].second;
if(v1[1].first==a[i])
v[1].pob();
v1[1]= {a[i], r+1};
v[1].pb({a[i], r+1});
}
else if(a[i]>v1[mx].first)
{
q=upper_bound(v[mx].begin(), v[mx].end(), a[i], comp_pair_int_rev() )-v[mx].begin();
if(q==0)
{
r=v1[mx].second;
}
else
{
r=v1[mx].second-v[mx][q-1].second;
}
v1[++mx]= {a[i], r};
v[mx].pb({a[i], r});
}
else if(a[i]==v1[mx].first)
{
q=upper_bound(v[mx-1].begin(), v[mx-1].end(), a[i], comp_pair_int_rev() )-v[mx-1].begin();
if(q==0)
{
r=v1[mx-1].second;
}
else
{
r=v1[mx-1].second-v[mx-1][q-1].second;
}
p=v1[mx].second;
v1[mx]= {a[i], p+r};
v[mx].pob();
v[mx].pb({a[i], p+r});
}
else
{
p=lower_bound(v1.begin()+1, v1.begin()+mx+1, a[i], comp_pair_int() )-v1.begin();
t=v1[p].second;
if(v1[p].first==a[i])
{
v[p].pob();
}
q=upper_bound(v[p-1].begin(), v[p-1].end(), a[i], comp_pair_int_rev() )-v[p-1].begin();
if(q==0)
{
r=v1[p-1].second;
}
else
{
r=v1[p-1].second-v[p-1][q-1].second;
}
v1[p]= {a[i], t+r};
v[p].pb({a[i], t+r});
}
}
cout<<v1[mx].second;
return 0;
}
Хотя я полностью согласен с Алексом, это можно сделать очень легко с помощью дерева сегментов. Вот логика для определения длины LIS с использованием дерева сегментов в NlogN. https://www.quora.com/What-is-the-approach-to-find-the-length-of-the-strictly-increasing-longest-subsequence Вот подход, который не находит LIS, но принимает N^2 сложности. https://codeforces.com/blog/entry/48677
Мы используем дерево сегментов (как здесь), чтобы оптимизировать подход, приведенный в этом. Вот логика:
сначала отсортируйте массив в порядке возрастания (также сохраните исходный порядок), инициализируйте дерево сегментов с нулями, дерево сегментов должно запросить две вещи (используйте для этого пару) для заданного диапазона: a. Макс первый. б. сумма второго, соответствующего max-first. перебрать отсортированный массив. пусть j будет исходным индексом текущего элемента, тогда мы запросим (0 - j-1) и обновим j-й элемент (если результат запроса равен 0,0, то мы обновим его с помощью (1,1)).
Вот мой код на C++:
#include<bits/stdc++.h>
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll int,ll int>
#define vi vector<ll int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll int)x.size()
#define hell 1000000007
#define rep(i,a,b) for(ll int i=a;i<b;i++)
#define lbnd lower_bound
#define ubnd upper_bound
#define bs binary_search
#define mp make_pair
using namespace std;
#define N 100005
ll max(ll a , ll b)
{
if( a > b) return a ;
else return
b;
}
ll n,l,r;
vector< pii > seg(4*N);
pii query(ll cur,ll st,ll end,ll l,ll r)
{
if(l<=st&&r>=end)
return seg[cur];
if(r<st||l>end)
return mp(0,0); /* 2-change here */
ll mid=(st+end)>>1;
pii ans1=query(2*cur,st,mid,l,r);
pii ans2=query(2*cur+1,mid+1,end,l,r);
if(ans1.F>ans2.F)
return ans1;
if(ans2.F>ans1.F)
return ans2;
return make_pair(ans1.F,ans2.S+ans1.S); /* 3-change here */
}
void update(ll cur,ll st,ll end,ll pos,ll upd1, ll upd2)
{
if(st==end)
{
// a[pos]=upd; /* 4-change here */
seg[cur].F=upd1;
seg[cur].S=upd2; /* 5-change here */
return;
}
ll mid=(st+end)>>1;
if(st<=pos&&pos<=mid)
update(2*cur,st,mid,pos,upd1,upd2);
else
update(2*cur+1,mid+1,end,pos,upd1,upd2);
seg[cur].F=max(seg[2*cur].F,seg[2*cur+1].F);
if(seg[2*cur].F==seg[2*cur+1].F)
seg[cur].S = seg[2*cur].S+seg[2*cur+1].S;
else
{
if(seg[2*cur].F>seg[2*cur+1].F)
seg[cur].S = seg[2*cur].S;
else
seg[cur].S = seg[2*cur+1].S;
/* 6-change here */
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int TESTS=1;
// cin>>TESTS;
while(TESTS--)
{
int n ;
cin >> n;
vector< pii > arr(n);
rep(i,0,n)
{
cin >> arr[i].F;
arr[i].S = -i;
}
sort(all(arr));
update(1,0,n-1,-arr[0].S,1,1);
rep(i,1,n)
{
pii x = query(1,0,n-1,-1,-arr[i].S - 1 );
update(1,0,n-1,-arr[i].S,x.F+1,max(x.S,1));
}
cout<<seg[1].S;//answer
}
return 0;
}
Сортировка терпения также O(N*logN), но намного короче и проще, чем методы, основанные на бинарном поиске:
static int[] input = {4, 5, 2, 8, 9, 3, 6, 2, 7, 8, 6, 6, 7, 7, 3, 6};
/**
* Every time a value is tested it either adds to the length of LIS (by calling decs.add() with it), or reduces the remaining smaller cards that must be found before LIS consists of smaller cards. This way all inputs/cards contribute in one way or another (except if they're equal to the biggest number in the sequence; if want't to include in sequence, replace 'card <= decs.get(decIndex)' with 'card < decs.get(decIndex)'. If they're bigger than all decs, they add to the length of LIS (which is something we want), while if they're smaller than a dec, they replace it. We want this, because the smaller the biggest dec is, the smaller input we need before we can add onto LIS.
*
* If we run into a decreasing sequence the input from this sequence will replace each other (because they'll always replace the leftmost dec). Thus this algorithm won't wrongfully register e.g. {2, 1, 3} as {2, 3}, but rather {2} -> {1} -> {1, 3}.
*
* WARNING: This can only be used to find length, not actual sequence, seeing how parts of the sequence will be replaced by smaller numbers trying to make their sequence dominate
*
* Due to bigger decs being added to the end/right of 'decs' and the leftmost decs always being the first to be replaced with smaller decs, the further a dec is to the right (the bigger it's index), the bigger it must be. Thus, by always replacing the leftmost decs, we don't run the risk of replacing the biggest number in a sequence (the number which determines if more cards can be added to that sequence) before a sequence with the same length but smaller numbers (thus currently equally good, due to length, and potentially better, due to less needed to increase length) has been found.
*/
static void patienceFindLISLength() {
ArrayList<Integer> decs = new ArrayList<>();
inputLoop: for (Integer card : input) {
for (int decIndex = 0; decIndex < decs.size(); decIndex++) {
if (card <= decs.get(decIndex)) {
decs.set(decIndex, card);
continue inputLoop;
}
}
decs.add(card);
}
System.out.println(decs.size());
}
Саша Салау, ответ отличный, но я не понимаю, почему
sum -= pRow.get(index).sum;
вот мой код, основанный на той же идее
import java.math.BigDecimal;
import java.util.*;
class lisCount {
static BigDecimal lisCount(int[] a) {
class Container {
Integer v;
BigDecimal count;
Container(Integer v) {
this.v = v;
}
}
List<List<Container>> lisIdxSeq = new ArrayList<List<Container>>();
int lisLen, lastIdx;
List<Container> lisSeqL;
Container lisEle;
BigDecimal count;
int pre;
for (int i = 0; i < a.length; i++){
pre = -1;
count = new BigDecimal(1);
lisLen = lisIdxSeq.size();
lastIdx = lisLen - 1;
lisEle = new Container(i);
if(lisLen == 0 || a[i] > a[lisIdxSeq.get(lastIdx).get(0).v]){
// lis len increased
lisSeqL = new ArrayList<Container>();
lisSeqL.add(lisEle);
lisIdxSeq.add(lisSeqL);
pre = lastIdx;
}else{
int h = lastIdx;
int l = 0;
while(l < h){
int m = (l + h) / 2;
if(a[lisIdxSeq.get(m).get(0).v] < a[i]) l = m + 1;
else h = m;
}
List<Container> lisSeqC = lisIdxSeq.get(l);
if(a[i] <= a[lisSeqC.get(0).v]){
int hi = lisSeqC.size() - 1;
int lo = 0;
while(hi < lo){
int mi = (hi + lo) / 2;
if(a[lisSeqC.get(mi).v] < a[i]) lo = mi + 1;
else hi = mi;
}
lisSeqC.add(lo, lisEle);
pre = l - 1;
}
}
if(pre >= 0){
Iterator<Container> it = lisIdxSeq.get(pre).iterator();
count = new BigDecimal(0);
while(it.hasNext()){
Container nt = it.next();
if(a[nt.v] < a[i]){
count = count.add(nt.count);
}else break;
}
}
lisEle.count = count;
}
BigDecimal rst = new BigDecimal(0);
Iterator<Container> i = lisIdxSeq.get(lisIdxSeq.size() - 1).iterator();
while(i.hasNext()){
rst = rst.add(i.next().count);
}
return rst;
}
public static void main(String[] args) {
System.out.println(lisCount(new int[] { 1, 3, 2, 2, 4 }));
System.out.println(lisCount(new int[] { 3, 2, 1 }));
System.out.println(lisCount(new int[] { 16, 5, 8, 6, 1, 10, 5, 2, 15, 3, 2, 4, 1 }));
}
}