Solución:
Bien, describiré primero la solución más simple que es O (N ^ 2), donde N es el tamaño de la colección. También existe una solución O (N log N), que también describiré. Búsquelo aquí en la sección Algoritmos eficientes.
Asumiré que los índices de la matriz son de 0 a N – 1. Así que definamos DP[i] para ser la longitud del LIS (subsecuencia creciente más larga) que termina en el elemento con índice i. Computar DP[i] miramos todos los índices j < i y compruebe ambos si DP[j] + 1 > DP[i] y array[j] < array[i] (queremos que esté aumentando). Si esto es cierto, podemos actualizar el óptimo actual para DP[i]. Para encontrar el óptimo global para la matriz, puede tomar el valor máximo de DP[0...N - 1].
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
Yo uso la matriz prev para luego poder encontrar la secuencia real no solo su longitud. Vuelve recursivamente desde bestEnd en un bucle usando prev[bestEnd]. los -1 El valor es una señal para detenerse.
OK, ahora a los más eficientes O(N log N) solución:
Dejar S[pos] definirse como el número entero más pequeño que finaliza una secuencia creciente de longitud pos. Ahora itera a través de cada entero X del conjunto de entrada y haga lo siguiente:
-
Si
X> último elemento enS, luego agregueXhasta el final deS. Esto esencialmente significa que hemos encontrado un nuevo mayorLIS. -
De lo contrario, encuentre el elemento más pequeño en
S, cual es>=queXy cámbielo aX. PorqueSse ordena en cualquier momento, el elemento se puede encontrar mediante la búsqueda binaria enlog(N).
Tiempo de ejecución total – N enteros y una búsqueda binaria para cada uno de ellos – N * log (N) = O (N log N)
Ahora hagamos un ejemplo real:
Colección de enteros:
2 6 3 4 1 2 9 5 8
Pasos:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
Entonces la longitud del LIS es 5 (el tamaño de S).
Para reconstruir el actual LIS de nuevo usaremos una matriz principal. Dejar parent[i] ser el predecesor del elemento con índice i en el LIS terminando en el elemento con índice i.
Para simplificar las cosas, podemos mantener en la matriz S, no los números enteros reales, sino sus índices (posiciones) en el conjunto. No mantenemos {1, 2, 4, 5, 8}, pero mantén {4, 5, 3, 7, 8}.
Que es entrada[4] = 1, aporte[5] = 2, aporte[3] = 4, aporte[7] = 5, aporte[8] = 8.
Si actualizamos correctamente la matriz principal, el LIS real es:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
Ahora a lo importante: ¿cómo actualizamos la matriz principal? Hay dos opciones:
-
Si
X> último elemento enS, luegoparent[indexX] = indexLastElement. Esto significa que el padre del elemento más nuevo es el último elemento. Solo anteponemosXhasta el final deS. -
De lo contrario, busque el índice del elemento más pequeño en
S, cual es>=queXy cámbielo aX. Aquíparent[indexX] = S[index - 1].
La explicación de Petar Minchev me ayudó a aclarar las cosas, pero me resultó difícil analizar qué era todo, así que hice una implementación de Python con nombres de variables demasiado descriptivos y muchos comentarios. Hice una solución recursiva ingenua, la solución O (n ^ 2) y la solución O (n log n).
¡Espero que ayude a aclarar los algoritmos!
La solución recursiva
def recursive_solution(remaining_sequence, bigger_than=None):
"""Finds the longest increasing subsequence of remaining_sequence that is
bigger than bigger_than and returns it. This solution is O(2^n)."""
# Base case: nothing is remaining.
if len(remaining_sequence) == 0:
return remaining_sequence
# Recursive case 1: exclude the current element and process the remaining.
best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)
# Recursive case 2: include the current element if it's big enough.
first = remaining_sequence[0]
if (first > bigger_than) or (bigger_than is None):
sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)
# Choose whichever of case 1 and case 2 were longer.
if len(sequence_with) >= len(best_sequence):
best_sequence = sequence_with
return best_sequence
La solución de programación dinámica O (n ^ 2)
def dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming. This solution is O(n^2)."""
longest_subsequence_ending_with = []
backreference_for_subsequence_ending_with = []
current_best_end = 0
for curr_elem in range(len(sequence)):
# It's always possible to have a subsequence of length 1.
longest_subsequence_ending_with.append(1)
# If a subsequence is length 1, it doesn't have a backreference.
backreference_for_subsequence_ending_with.append(None)
for prev_elem in range(curr_elem):
subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)
# If the prev_elem is smaller than the current elem (so it's increasing)
# And if the longest subsequence from prev_elem would yield a better
# subsequence for curr_elem.
if ((sequence[prev_elem] < sequence[curr_elem]) and
(subsequence_length_through_prev >
longest_subsequence_ending_with[curr_elem])):
# Set the candidate best subsequence at curr_elem to go through prev.
longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
backreference_for_subsequence_ending_with[curr_elem] = prev_elem
# If the new end is the best, update the best.
if (longest_subsequence_ending_with[curr_elem] >
longest_subsequence_ending_with[current_best_end]):
current_best_end = curr_elem
# Output the overall best by following the backreferences.
best_subsequence = []
current_backreference = current_best_end
while current_backreference is not None:
best_subsequence.append(sequence[current_backreference])
current_backreference = (backreference_for_subsequence_ending_with[current_backreference])
best_subsequence.reverse()
return best_subsequence
La solución de programación dinámica O (n log n)
def find_smallest_elem_as_big_as(sequence, subsequence, elem):
"""Returns the index of the smallest element in subsequence as big as
sequence[elem]. sequence[elem] must not be larger than every element in
subsequence. The elements in subsequence are indices in sequence. Uses
binary search."""
low = 0
high = len(subsequence) - 1
while high > low:
mid = (high + low) / 2
# If the current element is not as big as elem, throw out the low half of
# sequence.
if sequence[subsequence[mid]] < sequence[elem]:
low = mid + 1
# If the current element is as big as elem, throw out everything bigger, but
# keep the current element.
else:
high = mid
return high
def optimized_dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming and binary search (per
http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution
is O(n log n)."""
# Both of these lists hold the indices of elements in sequence and not the
# elements themselves.
# This list will always be sorted.
smallest_end_to_subsequence_of_length = []
# This array goes along with sequence (not
# smallest_end_to_subsequence_of_length). Following the corresponding element
# in this array repeatedly will generate the desired subsequence.
parent = [None for _ in sequence]
for elem in range(len(sequence)):
# We're iterating through sequence in order, so if elem is bigger than the
# end of longest current subsequence, we have a new longest increasing
# subsequence.
if (len(smallest_end_to_subsequence_of_length) == 0 or
sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
# If we are adding the first element, it has no parent. Otherwise, we
# need to update the parent to be the previous biggest element.
if len(smallest_end_to_subsequence_of_length) > 0:
parent[elem] = smallest_end_to_subsequence_of_length[-1]
smallest_end_to_subsequence_of_length.append(elem)
else:
# If we can't make a longer subsequence, we might be able to make a
# subsequence of equal size to one of our earlier subsequences with a
# smaller ending number (which makes it easier to find a later number that
# is increasing).
# Thus, we look for the smallest element in
# smallest_end_to_subsequence_of_length that is at least as big as elem
# and replace it with elem.
# This preserves correctness because if there is a subsequence of length n
# that ends with a number smaller than elem, we could add elem on to the
# end of that subsequence to get a subsequence of length n+1.
location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
smallest_end_to_subsequence_of_length[location_to_replace] = elem
# If we're replacing the first element, we don't need to update its parent
# because a subsequence of length 1 has no parent. Otherwise, its parent
# is the subsequence one shorter, which we just added onto.
if location_to_replace != 0:
parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])
# Generate the longest increasing subsequence by backtracking through parent.
curr_parent = smallest_end_to_subsequence_of_length[-1]
longest_increasing_subsequence = []
while curr_parent is not None:
longest_increasing_subsequence.append(sequence[curr_parent])
curr_parent = parent[curr_parent]
longest_increasing_subsequence.reverse()
return longest_increasing_subsequence
Hablando de la solución DP, me sorprendió que nadie mencionara el hecho de que LIS se puede reducir a LCS. Todo lo que necesita hacer es ordenar la copia de la secuencia original, eliminar todos los duplicados y hacer LCS de ellos. En pseudocódigo es:
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
Y la implementación completa escrita en Go. No necesita mantener la matriz n ^ 2 DP completa si no necesita reconstruir la solución.
func lcs(arr1 []int) int {
arr2 := make([]int, len(arr1))
for i, v := range arr1 {
arr2[i] = v
}
sort.Ints(arr1)
arr3 := []int{}
prev := arr1[0] - 1
for _, v := range arr1 {
if v != prev {
prev = v
arr3 = append(arr3, v)
}
}
n1, n2 := len(arr1), len(arr3)
M := make([][]int, n2 + 1)
e := make([]int, (n1 + 1) * (n2 + 1))
for i := range M {
M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)]
}
for i := 1; i <= n2; i++ {
for j := 1; j <= n1; j++ {
if arr2[j - 1] == arr3[i - 1] {
M[i][j] = M[i - 1][j - 1] + 1
} else if M[i - 1][j] > M[i][j - 1] {
M[i][j] = M[i - 1][j]
} else {
M[i][j] = M[i][j - 1]
}
}
}
return M[n2][n1]
}