Найти наиболее продолжительную последовательность

Ответ 1

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

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

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

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

• 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] (самая длинная возрастающая подпоследовательность)

Ответ 2

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

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

Ответ 3

на основе ответа 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();
}

}

Ответ 4

Ниже приведена самая длинная возрастающая подпоследовательность 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 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;
    }

Ответ 5

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

M [i] - индекс последнего элемента последовательности, длина которого равна i, P [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;
}

Ответ 6

Поздно к вечеринке, но вот реализация 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;
};

Ответ 7

мы можем реализовать его в двух массивах 2d подобная последовательность

 8    2     4
 0    7     1
 3    7     9

и LIS 0 → 2 → 4 → 7 → 8  и что такое алгоритм для этого