Ответ 1

Поиск числа всех длительно растущих подпоследовательностей

Полный Java-код улучшенного алгоритма LIS, который обнаруживает не только длину самой длинной возрастающей подпоследовательности, но и число подпоследовательностей такой длины. Я предпочитаю использовать generics, чтобы не только целые числа, но и любые сопоставимые типы.

@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". Таким образом, задача состоит в том, чтобы вычислить количество самых длинных увеличивающихся субмарок, которые могут быть получены из seq.

Как я упоминал ранее, идея состоит в том, чтобы вести учет всех возможных дольше, полученных на предыдущих шагах. Поэтому позвольте создать пронумерованный список строк, где число каждой строки равно длине субмасок, хранящихся в этой строке. И пусть store subs как пары чисел (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. Он не может создать sub [16, 8] длины 2, но может создать sub [5, 8]. Итак, вот где идет алгоритм. Во-первых, мы перебираем строки списка вверх ногами, глядя на "значения" последней пары. Если наш элемент больше, чем значения всех последних элементов во всех строках, мы можем добавить его к существующим sub (s), увеличивая его длину на единицу. Таким образом, значение 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 в subs длиной 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 ²) не то, что мы хотим.

Во-первых, очевидно, что в каждом промежуточном состоянии строки сортируются по возрастанию порядка их последнего "значения". Таким образом, вместо грубой петли может выполняться двоичный поиск, сложность которого - O (log n).

Во-вторых, нам не нужно суммировать "подсчеты" подсетей путем циклического обращения к элементам строки каждый раз. Мы можем суммировать их в процессе, когда новая пара добавляется в строку, например:

1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row

Таким образом, второе число покажет не количество самых длинных субмарок, которые могут быть получены с заданным значением в конце, но суммарный подсчет всех самых длинных субмарок, которые заканчиваются любым элементом, который больше или равен "значению" из пары.

Таким образом, "counts" будет заменен на "sums". И вместо повторения элементов в предыдущей строке мы просто выполняем двоичный поиск (это возможно, потому что пары в любой строке всегда упорядочены по их "значениям" ) и берут "сумму" для новой пары как "сумму" последнего элемента в предыдущей строке минус "сумма" от элемента слева до найденного положения в предыдущей строке плюс "сумма" предыдущего элемента в текущей строке.

Поэтому при обработке 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), потому что мы не делаем никакой сортировки и перегруппировки во время процесса. Поэтому оценка сложности кажется окончательной.

Ответ 2

Саша Салауу отвечает, но я не понимаю, почему

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

Ответ 3

Сортировка терпения также 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 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());
}

Ответ 4

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;
}

Ответ 5

Хотя я полностью согласен с Алексом, это можно сделать очень легко с помощью дерева сегментов. Вот логика для определения длины LIS с использованием дерева сегментов в NlogN. https://www.quora.com/What-is-the-approach-to-find-the-length-of-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;
}