Comment déterminer la séquence la plus longue de plus en plus en utilisant la programmation dynamique?
https://stackoverflow.com/questions/2631726
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai un ensemble d'entiers. Je veux trouver de cet ensemble la plus longue suite croissante en utilisant la programmation dynamique.
La solution
OK, je vais décrire d'abord la solution la plus simple qui est O (N ^ 2), où N est la taille de la collection. solution Il existe également un O (N log N), que je vais décrire aussi. Regardez pour cela à la section des algorithmes efficaces.
Je vais assumer les indices du tableau sont de 0 à N - 1. Donc, nous allons définir DP[i] être la longueur de la LIS (la plus longue séquence de plus en plus) qui se termine à l'élément avec un indice i. Pour DP[i] Compute nous regardons tous les indices j < i et vérifier à la fois si DP[j] + 1 > DP[i] et array[j] < array[i] (nous voulons qu'il soit de plus en plus). Si cela est vrai, nous pouvons mettre à jour l'optimum en cours pour DP[i]. Pour trouver l'optimum global pour le réseau, vous pouvez prendre la valeur maximale 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];
}
}
J'utilise le prev de tableau pour pouvoir plus tard pour trouver la séquence réelle non seulement sa longueur. Il suffit de revenir en arrière récursive de bestEnd dans une boucle en utilisant prev[bestEnd]. La valeur -1 est un signe d'arrêt.
OK, maintenant à la solution O(N log N) plus efficace:
Soit S[pos] être définie comme le plus petit entier qui met fin à une séquence croissante de pos de longueur. Maintenant itérer à travers tous les X entier de l'ensemble d'entrée et procédez comme suit:
-
Si
X> dernier élémentS, puis appendXà la fin deS. Ce moyen essentialy nous avons trouvé un nouveau plus grandLIS. -
trouver Sinon le plus petit élément
S, qui est>=queX, et le changer àX. Parce queSest triée à tout moment, l'élément peut être trouvé en utilisant la recherche binaire danslog(N).
durée totale d'exécution - entiers N et une recherche binaire pour chacun d'eux - N * log (N) = O (N log N)
Maintenant, nous allons faire un exemple réel:
Collection d'entiers:
2 6 3 4 1 2 9 5 8
Étapes:
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
Ainsi, la longueur de la LIS est 5 (la taille de S).
Pour reconstruire le LIS réelle, nous utiliserons à nouveau un tableau parent.
Que parent[i] soit le prédécesseur de l'élément avec i d'index dans l'LIS se terminant à l'élément avec l'index i.
Pour rendre les choses plus simples, nous pouvons garder dans le S tableau, pas les entiers réels, mais leurs indices (positions) dans l'ensemble. Nous ne gardons pas {1, 2, 4, 5, 8}, mais gardez {4, 5, 3, 7, 8}.
Cela est entrée [4] = 1 , entrée [5] = 2 , entrée [3] = 4 , entrée [7 ] = 5 , entrée [8] = 8 .
Si nous mettons à jour correctement le tableau parent, la LIS est réelle:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
Maintenant, pour ce qui est important - comment pouvons-nous mettre à jour le tableau de parent? Il y a deux options:
-
Si
X> dernier élémentS, puisparent[indexX] = indexLastElement. Cela signifie que le parent du dernier élément est le dernier élément. Nous venons précédezXà la fin deS. -
trouver Sinon l'index de l'élément le plus petit dans
S, qui est>=queX, et le changer àX. Iciparent[indexX] = S[index - 1].
Autres conseils
L'explication de Petar Minchev a contribué à clarifier les choses pour moi, mais il m'a été difficile d'analyser ce que tout était, donc je fait une implémentation Python avec des noms de variables trop descriptifs et beaucoup de commentaires. Je l'ai fait une solution récursive naïve, la solution O (n ^ 2), et la solution O (n log n).
J'espère que cela aide à éclaircir les algorithmes!
La solution récursive
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
O (n ^ 2) Programmation Dynamique Solution
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
O (log n n) de programmation dynamique Solution
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
En parlant de solution DP, je l'ai trouvé surprenant que personne ne mentionne le fait que LIS peut être réduite à LCS . Tout ce que vous devez faire est sorte la copie de la séquence d'origine, supprimer tous les doublons et faire LCS d'entre eux. En pseudocode il est:
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
Et la pleine mise en œuvre écrite en Go. Vous n'avez pas besoin de maintenir l'ensemble n ^ 2 matrice DP si vous n'avez pas besoin de reconstruire la solution.
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]
}
Ce qui suit la mise en œuvre C de comprend également un code qui construit le réel plus long croissante séquence à l'aide d'un tableau appelé prev.
std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
int best_end = 0;
int sz = s.size();
if (!sz)
return std::vector<int>();
std::vector<int> prev(sz,-1);
std::vector<int> memo(sz, 0);
int max_length = std::numeric_limits<int>::min();
memo[0] = 1;
for ( auto i = 1; i < sz; ++i)
{
for ( auto j = 0; j < i; ++j)
{
if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
{
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if ( memo[i] > max_length )
{
best_end = i;
max_length = memo[i];
}
}
// Code that builds the longest increasing subsequence using "prev"
std::vector<int> results;
results.reserve(sz);
std::stack<int> stk;
int current = best_end;
while (current != -1)
{
stk.push(s[current]);
current = prev[current];
}
while (!stk.empty())
{
results.push_back(stk.top());
stk.pop();
}
return results;
}
La mise en œuvre sans pile juste inverser le vecteur
#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
auto sz = v.size();
if(!sz)
return v;
std::vector<int> memo(sz, 0);
std::vector<int> prev(sz, -1);
memo[0] = 1;
int best_end = 0;
int max_length = std::numeric_limits<int>::min();
for (auto i = 1; i < sz; ++i) {
for ( auto j = 0; j < i ; ++j) {
if (s[j] < s[i] && memo[i] < memo[j] + 1) {
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if(memo[i] > max_length) {
best_end = i;
max_length = memo[i];
}
}
// create results
std::vector<int> results;
results.reserve(v.size());
auto current = best_end;
while (current != -1) {
results.push_back(s[current]);
current = prev[current];
}
std::reverse(results.begin(), results.end());
return results;
}
Voici trois étapes consistant à évaluer le problème du point de vue de la programmation dynamique:
- définition Récurrence: maxLength (i) == 1 + maxLength (j) où 0
array [j] - Récurrence paramètre de limite: il peut y avoir 0 à i - 1 sous-séquences transmises en tant que paramter
- ordre d'évaluation, selon qu'il est sous-séquence croissante, il doit être évaluée de 0 à n
Si l'on prend comme exemple de séquence {0, 8, 2, 3, 7, 9}, à l'index:
- [0] nous obtenons {0} séquence comme un cas de base
- [1], nous avons 1 {0 nouvelle séquence, 8}
- [2] essayer d'évaluer deux nouvelles séquences {0, 8, 2} et {0, 2} par élément ajoutant à l'index 2 à des sous-séquences existantes - un seul est valable, afin d'ajouter la troisième séquence possible {0, 2} uniquement à la liste des paramètres ...
Voici le C ++ 11 travail code:
#include <iostream>
#include <vector>
int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
if(index == 0) {
sub.push_back(std::vector<int>{sequence[0]});
return 1;
}
size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
std::vector<std::vector<int>> tmpSubSeq;
for(std::vector<int> &subSeq : sub) {
if(subSeq[subSeq.size() - 1] < sequence[index]) {
std::vector<int> newSeq(subSeq);
newSeq.push_back(sequence[index]);
longestSubSeq = std::max(longestSubSeq, newSeq.size());
tmpSubSeq.push_back(newSeq);
}
}
std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
std::back_insert_iterator<std::vector<std::vector<int>>>(sub));
return longestSubSeq;
}
int getLongestIncSub(const std::vector<int> &sequence) {
std::vector<std::vector<int>> sub;
return getLongestIncSub(sequence, sequence.size() - 1, sub);
}
int main()
{
std::vector<int> seq{0, 8, 2, 3, 7, 9};
std::cout << getLongestIncSub(seq);
return 0;
}
Voici une implémentation Scala de l'O (n ^ 2) algorithme:
object Solve {
def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
xs.foldLeft(List[(Int, List[T])]()) {
(sofar, x) =>
if (sofar.isEmpty) List((1, List(x)))
else {
val resIfEndsAtCurr = (sofar, xs).zipped map {
(tp, y) =>
val len = tp._1
val seq = tp._2
if (ord.lteq(y, x)) {
(len + 1, x :: seq) // reversely recorded to avoid O(n)
} else {
(1, List(x))
}
}
sofar :+ resIfEndsAtCurr.maxBy(_._1)
}
}.maxBy(_._1)._2.reverse
}
def main(args: Array[String]) = {
println(longestIncrSubseq(List(
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)))
}
}
Voici une autre O (n ^ 2) de mise en œuvre JAVA. Pas de récursion / memoization pour générer la séquence réelle. Juste un tableau de chaînes qui stocke les LIS réelles à chaque étape et un tableau pour stocker la longueur de la LIS pour chaque élément. Sacrément facile. Jetez un coup d'oeil:
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
* Created by Shreyans on 4/16/2015
*/
class LNG_INC_SUB//Longest Increasing Subsequence
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter Numbers Separated by Spaces to find their LIS\n");
String[] s1=br.readLine().split(" ");
int n=s1.length;
int[] a=new int[n];//Array actual of Numbers
String []ls=new String[n];// Array of Strings to maintain LIS for every element
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s1[i]);
}
int[]dp=new int[n];//Storing length of max subseq.
int max=dp[0]=1;//Defaults
String seq=ls[0]=s1[0];//Defaults
for(int i=1;i<n;i++)
{
dp[i]=1;
String x="";
for(int j=i-1;j>=0;j--)
{
//First check if number at index j is less than num at i.
// Second the length of that DP should be greater than dp[i]
// -1 since dp of previous could also be one. So we compare the dp[i] as empty initially
if(a[j]<a[i]&&dp[j]>dp[i]-1)
{
dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j]
x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on
}
}
x+=(" "+a[i]);
ls[i]=x;
if(dp[i]>max)
{
max=dp[i];
seq=ls[i];
}
}
System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq);
}
}
Code de l'action: http://ideone.com/sBiOQx
Ceci peut être résolu en O (n ^ 2) en utilisant la programmation dynamique. code Python pour le même serait comme: -
def LIS(numlist):
LS = [1]
for i in range(1, len(numlist)):
LS.append(1)
for j in range(0, i):
if numlist[i] > numlist[j] and LS[i]<=LS[j]:
LS[i] = 1 + LS[j]
print LS
return max(LS)
numlist = map(int, raw_input().split(' '))
print LIS(numlist)
Pour l'entrée: 5 19 5 81 50 28 29 1 83 23
sortie serait: [1, 2, 1, 3, 3, 3, 4, 1, 5, 3]
5
Le list_index de la liste de sortie est la list_index de liste d'entrée. La valeur à une list_index donnée dans la liste de sortie indique la longueur de la plus longue sous-séquence croissante pour que list_index.
est ici java O (nlogn) mise en œuvre
import java.util.Scanner;
public class LongestIncreasingSeq {
private static int binarySearch(int table[],int a,int len){
int end = len-1;
int beg = 0;
int mid = 0;
int result = -1;
while(beg <= end){
mid = (end + beg) / 2;
if(table[mid] < a){
beg=mid+1;
result = mid;
}else if(table[mid] == a){
return len-1;
}else{
end = mid-1;
}
}
return result;
}
public static void main(String[] args) {
// int[] t = {1, 2, 5,9,16};
// System.out.println(binarySearch(t , 9, 5));
Scanner in = new Scanner(System.in);
int size = in.nextInt();//4;
int A[] = new int[size];
int table[] = new int[A.length];
int k = 0;
while(k<size){
A[k++] = in.nextInt();
if(k<size-1)
in.nextLine();
}
table[0] = A[0];
int len = 1;
for (int i = 1; i < A.length; i++) {
if(table[0] > A[i]){
table[0] = A[i];
}else if(table[len-1]<A[i]){
table[len++]=A[i];
}else{
table[binarySearch(table, A[i],len)+1] = A[i];
}
}
System.out.println(len);
}
}
Ceci est une implémentation Java en O (n ^ 2). Je n'ai pas utilisé Binary Search pour trouver le plus petit élément S, qui est> = que X. Je viens d'utiliser une boucle. En utilisant Binary Search serait la complexité à O (n log n)
public static void olis(int[] seq){
int[] memo = new int[seq.length];
memo[0] = seq[0];
int pos = 0;
for (int i=1; i<seq.length; i++){
int x = seq[i];
if (memo[pos] < x){
pos++;
memo[pos] = x;
} else {
for(int j=0; j<=pos; j++){
if (memo[j] >= x){
memo[j] = x;
break;
}
}
}
//just to print every step
System.out.println(Arrays.toString(memo));
}
//the final array with the LIS
System.out.println(Arrays.toString(memo));
System.out.println("The length of lis is " + (pos + 1));
}
commander le code Java pour augmenter la plus longue séquence avec les éléments du tableau
/**
** Java Program to implement Longest Increasing Subsequence Algorithm
**/
import java.util.Scanner;
/** Class LongestIncreasingSubsequence **/
class LongestIncreasingSubsequence
{
/** function lis **/
public int[] lis(int[] X)
{
int n = X.length - 1;
int[] M = new int[n + 1];
int[] P = new int[n + 1];
int L = 0;
for (int i = 1; i < n + 1; i++)
{
int j = 0;
/** Linear search applied here. Binary Search can be applied too.
binary search for the largest positive j <= L such that
X[M[j]] < X[i] (or set j = 0 if no such value exists) **/
for (int pos = L ; pos >= 1; pos--)
{
if (X[M[pos]] < X[i])
{
j = pos;
break;
}
}
P[i] = M[j];
if (j == L || X[i] < X[M[j + 1]])
{
M[j + 1] = i;
L = Math.max(L,j + 1);
}
}
/** backtrack **/
int[] result = new int[L];
int pos = M[L];
for (int i = L - 1; i >= 0; i--)
{
result[i] = X[pos];
pos = P[pos];
}
return result;
}
/** Main Function **/
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Longest Increasing Subsequence Algorithm Test\n");
System.out.println("Enter number of elements");
int n = scan.nextInt();
int[] arr = new int[n + 1];
System.out.println("\nEnter "+ n +" elements");
for (int i = 1; i <= n; i++)
arr[i] = scan.nextInt();
LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence();
int[] result = obj.lis(arr);
/** print result **/
System.out.print("\nLongest Increasing Subsequence : ");
for (int i = 0; i < result.length; i++)
System.out.print(result[i] +" ");
System.out.println();
}
}
Ceci peut être résolu en O (n ^ 2) en utilisant la programmation dynamique.
Traiter les éléments d'entrée et pour maintenir une liste d'uplets pour chaque élément. Chaque tuple (A, B), pour l'élément i ne désigne, A = longueur de la plus longue sous-séquence croissante se terminant à i et B = indice de prédécesseur de liste [i] dans la plus longue sous-séquence croissante se terminant à la liste [i ].
Début de l'élément 1, la liste des tuple de l'élément 1 sera [(1,0)]
pour i élément, analyser la liste 0..i et liste des éléments trouver [k] de telle sorte que la liste [k] En fin de compte, de trouver tous les éléments ayant une valeur maximale de A (longueur de LIS se terminant à l'élément) et en utilisant les tuples retour en arrière pour obtenir la liste. J'ai partagé le code de même http://www.edufyme.com/code /? id = 66f041e16a60928b05a7e228a89c3799
O (n ^ 2) la mise en oeuvre de Java:
void LIS(int arr[]){
int maxCount[]=new int[arr.length];
int link[]=new int[arr.length];
int maxI=0;
link[0]=0;
maxCount[0]=0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if(arr[j]<arr[i] && ((maxCount[j]+1)>maxCount[i])){
maxCount[i]=maxCount[j]+1;
link[i]=j;
if(maxCount[i]>maxCount[maxI]){
maxI=i;
}
}
}
}
for (int i = 0; i < link.length; i++) {
System.out.println(arr[i]+" "+link[i]);
}
print(arr,maxI,link);
}
void print(int arr[],int index,int link[]){
if(link[index]==index){
System.out.println(arr[index]+" ");
return;
}else{
print(arr, link[index], link);
System.out.println(arr[index]+" ");
}
}
def longestincrsub(arr1):
n=len(arr1)
l=[1]*n
for i in range(0,n):
for j in range(0,i) :
if arr1[j]<arr1[i] and l[i]<l[j] + 1:
l[i] =l[j] + 1
l.sort()
return l[-1]
arr1=[10,22,9,33,21,50,41,60]
a=longestincrsub(arr1)
print(a)
même si il y a un moyen par lequel vous pouvez résoudre ce O (nlogn) temps (cela résoud en O (n ^ 2) temps), mais encore de cette façon donne l'approche de programmation dynamique qui est également bon.
Voici ma solution Leetcode en utilisant la recherche binaire: ->
class Solution:
def binary_search(self,s,x):
low=0
high=len(s)-1
flag=1
while low<=high:
mid=(high+low)//2
if s[mid]==x:
flag=0
break
elif s[mid]<x:
low=mid+1
else:
high=mid-1
if flag:
s[low]=x
return s
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
s=[]
s.append(nums[0])
for i in range(1,len(nums)):
if s[-1]<nums[i]:
s.append(nums[i])
else:
s=self.binary_search(s,nums[i])
return len(s)
solution la plus simple LIS en C ++ avec O (nlog (n)) complexité temporelle
#include <iostream>
#include "vector"
using namespace std;
// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
if(beg<=end)
{
int mid = (beg+end)/2;
if(a[mid] == value)
return mid;
else if(value < a[mid])
return ceilBinarySearch(a,beg,mid-1,value);
else
return ceilBinarySearch(a,mid+1,end,value);
return 0;
}
return beg;
}
int lis(vector<int> arr)
{
vector<int> dp(arr.size(),0);
int len = 0;
for(int i = 0;i<arr.size();i++)
{
int j = ceilBinarySearch(dp,0,len-1,arr[i]);
dp[j] = arr[i];
if(j == len)
len++;
}
return len;
}
int main()
{
vector<int> arr {2, 5,-1,0,6,1,2};
cout<<lis(arr);
return 0;
}
SORTIE:
4
