Найти самую длинную возрастающую последовательность

Question

Вам дана последовательность чисел, и вам нужно найти самую длинную возрастающую подпоследовательность из заданного ввода (необязательно непрерывного).

Я нашел ссылку на это ( Самая длинная увеличивающаяся подпоследовательность в Википедии ), но мне нужно больше объяснений.

Если кто-нибудь может помочь мне понять реализацию O (n log n), это будет действительно полезно. Если бы вы могли объяснить алгоритм с помощью примера, это будет действительно оценено.

Я видел и другие посты, и чего я не понял: L = 0 для i = 1, 2, ... n: бинарный поиск наибольшего положительного j ≤ L, такого что X [M [j]]

Answer 1

Более простая задача - найти длину самой длинной увеличивающейся подпоследовательности. Вы можете сосредоточиться на понимании этой проблемы в первую очередь. Единственное отличие в алгоритме состоит в том, что он не использует массив P .

x является вводом последовательности, поэтому его можно инициализировать как: x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

m отслеживает лучшую подпоследовательность каждой длины , найденную до сих пор. Наилучшим является тот, который имеет наименьшее конечное значение (после него можно добавить более широкий диапазон значений). Длина и конечное значение являются единственными данными, которые необходимо сохранить для каждой подпоследовательности.

Каждый элемент m представляет подпоследовательность. Для м [Дж] ,

• j - длина подпоследовательности.
• m [j] - индекс (в x ) последнего элемента подпоследовательности.
• , x [m [j]] - значение последнего элемента подпоследовательности.

L - длина самой длинной найденной подпоследовательности. Первые L значения m действительны, остальные не инициализированы. m может начинаться с того, что первый элемент равен 0, остальные неинициализированы. L увеличивается при запуске алгоритма, равно как и число инициализированных значений m .

Вот пример запуска. x [i] и m в конце каждой итерации (но вместо индексов используются значения последовательности).

Поиск в каждой итерации ищет место для размещения x [i] . Оно должно быть как можно дальше вправо (чтобы получить самую длинную последовательность) и быть больше значения слева от него (так что это возрастающая последовательность).

 0:  m = [0, 0]        - ([0] is a subsequence of length 1.)
 8:  m = [0, 0, 8]     - (8 can be added after [0] to get a sequence of length 2.)
 4:  m = [0, 0, 4]     - (4 is better than 8. This can be added after [0] instead.)
 12: m = [0, 0, 4, 12] - (12 can be added after [...4])
 2:  m = [0, 0, 2, 12] - (2 can be added after [0] instead of 4.)
 10: m = [0, 0, 2, 10]
 6:  m = [0, 0, 2, 6]
 14: m = [0, 0, 2, 6, 14]
 1:  m = [0, 0, 1, 6, 14]
 9:  m = [0, 0, 1, 6, 9]
 5:  m = [0, 0, 1, 5, 9]
 13: m = [0, 0, 1, 5, 9, 13]
 3:  m = [0, 0, 1, 3, 9, 13]
 11: m = [0, 0, 1, 3, 9, 11]
 7:  m = [0, 0, 1, 3, 7, 11]
 15: m = [0, 0, 1, 3, 7, 11, 15]

Теперь мы знаем, что есть подпоследовательность длины 6, заканчивающаяся 15. Фактические значения в подпоследовательности можно найти, сохранив их в массиве P во время цикла.

Получение лучшей подпоследовательности:

P сохраняет предыдущий элемент в самой длинной подпоследовательности (в виде индекса x) для каждого числа и обновляется по мере продвижения алгоритма. Например, когда мы обрабатываем 8, мы знаем, что оно идет после 0, поэтому сохраните факт, что 8 после 0, в P . Вы можете работать в обратном направлении от последнего номера, как связанный список, чтобы получить всю последовательность.

Так что для каждого номера мы знаем число, которое предшествовало ему. Чтобы найти подпоследовательность, заканчивающуюся на 7, мы смотрим на P и видим, что:

7 is after 3
3 is after 1
1 is after 0

Итак, у нас есть подпоследовательность [0, 1, 3, 7].

Подпоследовательности, заканчивающиеся на 7 или 15, разделяют несколько чисел:

15 is after 11
11 is after 9
9 is after 6
6 is after 2
2 is after 0

Итак, у нас есть подпоследовательности [0, 2, 6, 9, 11] и [0, 2, 6, 9, 11, 15] (самая длинная возрастающая подпоследовательность)

Answer 2

Одним из лучших объяснений этой проблемы является сайт MIT.http://people.csail.mit.edu/bdean/6.046/dp/

Надеюсь, это рассеет все ваши сомнения.

Answer 3

Ниже приведена самая длинная увеличивающаяся реализация подпоследовательности O (NLogN):

// search for the index which can be replaced by the X. as the index can't be
//0 or end (because if 0 then replace in the findLIS() and if it's greater than the 
//current maximum the just append)of the array "result" so most of the boundary 
//conditions are not required.
public static int search(int[] result, int p, int r, int x)
{
    if(p > r) return -1;
    int q = (p+r)/2;
    if(result[q] < x && result[q+1]>x)
    {
        return q+1;
    }
    else if(result[q] > x)
    {
        return search(result, p, q, x);
    }
    else
    {
        return search(result, q+1, r, x);
    }
}
    public static int findLIS(int[] a)
    {
        int[] result = new int[a.length];
        result[0] = a[0];
        int index = 0;
        for(int i=1; i<a.length; i++)
        {
            int no = a[i];
            if(no < result[0]) // replacing the min number
            {
                result[0] = no;
            }
            else if(no > result[index])//if the number is bigger then the current big then append
            {
                result[++index] = no;
            }
            else
            {
                int c = search(result, 0, index, no);
                result[c] = no;
            }
        }
        return index+1;
    }

Answer 4

на основе ответа FJB, реализация Java:

public class Lis {

private static int[] findLis(int[] arr) {
    int[] is = new int[arr.length];
    int index = 0;
    is[0] = index;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[is[index]]) {
            for (int j = 0; j <= index; j++) {
                if (arr[i] < arr[is[j]]) {
                    is[j] = i;
                    break;
                }
            }
        } else if (arr[i] == arr[is[index]]) {

        } else {
            is[++index] = i;
        }
    }

    int[] lis = new int[index + 1];
    lis[index] = arr[is[index]];

    for (int i = index - 1; i >= 0; i--) {
        if (is[i] < is[i + 1]) {
            lis[i] = arr[is[i]];
        } else {
            for (int j = is[i + 1] - 1; j >= 0; j--) {
                if (arr[j] > arr[is[i]] && arr[j] < arr[is[i + 1]]) {
                    lis[i] = arr[j];
                    is[i] = j;
                    break;
                }
            }
        }
    }

    return lis;
}

public static void main(String[] args) {
    int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11,
            7, 15 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();

    arr = new int[] { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();
}

}

Answer 5

Поздно на вечеринке, но вот реализация JavaScript, чтобы пойти вместе с другими ..:)

var findLongestSubsequence = function(array) {
  var longestPartialSubsequences = [];
  var longestSubsequenceOverAll = [];

  for (var i = 0; i < array.length; i++) {
    var valueAtI = array[i];
    var subsequenceEndingAtI = [];

    for (var j = 0; j < i; j++) {
      var subsequenceEndingAtJ = longestPartialSubsequences[j];
      var valueAtJ = array[j];

      if (valueAtJ < valueAtI && subsequenceEndingAtJ.length > subsequenceEndingAtI.length) {
        subsequenceEndingAtI = subsequenceEndingAtJ;
      }
    }

    longestPartialSubsequences[i] = subsequenceEndingAtI.concat();
    longestPartialSubsequences[i].push(valueAtI);

    if (longestPartialSubsequences[i].length > longestSubsequenceOverAll.length) {
      longestSubsequenceOverAll = longestPartialSubsequences[i];
    }
  }

  return longestSubsequenceOverAll;
};

Answer 6

Основываясь на ответе @fgb, я реализовал алгоритм, используя c ++, чтобы найти самую длинную строго возрастающую подпоследовательность. Надеюсь, это будет несколько полезно.

M [i] - это индекс последнего элемента последовательности, длина которого равна i, P [i] - это индекс предыдущего элемента i в последовательности, который используется для печати всей последовательности.

main () используется для запуска простого теста: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

#include <vector>
using std::vector;
int LIS(const vector<int> &v) {
  int size = v.size(), max_len = 1;
  // M[i] is the index of the last element of the sequence whose length is i
  int *M = new int[size];
  // P[i] is the index of the previous element of i in the sequence, which is used to print the whole sequence
  int *P = new int[size];
  M[0] = 0; P[0] = -1;
  for (int i = 1; i < size; ++i) {
    if (v[i] > v[M[max_len - 1]]) {
      M[max_len] = i;
      P[i] = M[max_len - 1];
      ++max_len;
      continue;
    }
    // Find the position to insert i using binary search
    int lo = 0, hi = max_len - 1;
    while (lo <= hi) {
      int mid = lo + ((hi - lo) >> 1);
      if (v[i] < v[M[mid]]) {
        hi = mid - 1;
      } else if (v[i] > v[M[mid]]) {
        lo = mid + 1;
      } else {
        lo = mid;
        break;
      }
    }
    P[i] = P[M[lo]];  // Modify the previous pointer
    M[lo] = i;  
  }
  // Print the whole subsequence
  int i = M[max_len - 1];
  while (i >= 0) {
    printf("%d ", v[i]);
    i = P[i];
  }
  printf("\n");
  delete[] M, delete[] P;
  return max_len;
}
int main(int argc, char* argv[]) {
  int data[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
  vector<int> v;
  v.insert(v.end(), data, data + sizeof(data) / sizeof(int));
  LIS(v);
  return 0;
}

Answer 7

можем ли мы реализовать это в два 2d массива как последовательность

 8    2     4
 0    7     1
 3    7     9

и LIS 0 -> 2 -> 4 -> 7 -> 8 и каков алгоритм для этого