// A Naive C++ recursive implementation // of LIS problem #include  using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end // with an element before arr[n-1] max_ref // is used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int _lis(int arr[], int n, int* max_ref) {  // Base case  if (n == 1)  return 1;  // 'max_ending_here' is length of  // LIS ending with arr[n-1]  int res, max_ending_here = 1;  // Recursively get all LIS ending with  // arr[0], arr[1] ... arr[n-2]. If  // arr[i-1] is smaller than arr[n-1],  // and max ending with arr[n-1] needs  // to be updated, then update it  for (int i = 1; i < n; i++) {  res = _lis(arr, i, max_ref);  if (arr[i - 1] < arr[n - 1]  && res + 1>max_ending_here) max_ending_here = res + 1;  } // Comparez max_ending_here avec le // max global. Et mettez à jour le // maximum global si nécessaire si (*max_ref< max_ending_here)  *max_ref = max_ending_here;  // Return length of LIS ending  // with arr[n-1]  return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) {  // The max variable holds the result  int max = 1;  // The function _lis() stores its  // result in max  _lis(arr, n, &max);  // Returns max  return max; } // Driver program to test above function int main() {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function call  cout << 'Length of lis is ' << lis(arr, n);  return 0; }>

// A Naive C recursive implementation // of LIS problem #include  #include  // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size n // is stored in *max_ref which is our final result int _lis(int arr[], int n, int* max_ref) {  // Base case  if (n == 1)  return 1;  // 'max_ending_here' is length of LIS  // ending with arr[n-1]  int res, max_ending_here = 1;  // Recursively get all LIS ending with arr[0],  // arr[1] ... arr[n-2]. If arr[i-1] is smaller  // than arr[n-1], and max ending with arr[n-1]  // needs to be updated, then update it  for (int i = 1; i < n; i++) {  res = _lis(arr, i, max_ref);  if (arr[i - 1] < arr[n - 1]  && res + 1>max_ending_here) max_ending_here = res + 1;  } // Comparez max_ending_here avec le // max. Et mettez à jour le maximum global si nécessaire si (*max_ref< max_ending_here)  *max_ref = max_ending_here;  // Return length of LIS ending with arr[n-1]  return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) {  // The max variable holds the result  int max = 1;  // The function _lis() stores its result in max  _lis(arr, n, &max);  // returns max  return max; } // Driver program to test above function int main() {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function call  printf('Length of lis is %d', lis(arr, n));  return 0; }>

// A Naive Java Program for LIS Implementation import java.io.*; import java.util.*; class LIS {  // Stores the LIS  static int max_ref;  // To make use of recursive calls, this function must  // return two things: 1) Length of LIS ending with  // element arr[n-1]. We use max_ending_here for this  // purpose 2) Overall maximum as the LIS may end with an  // element before arr[n-1] max_ref is used this purpose.  // The value of LIS of full array of size n is stored in  // *max_ref which is our final result  static int _lis(int arr[], int n)  {  // Base case  if (n == 1)  return 1;  // 'max_ending_here' is length of LIS ending with  // arr[n-1]  int res, max_ending_here = 1;  // Recursively get all LIS ending with arr[0],  // arr[1] ... arr[n-2]. If arr[i-1] is smaller  // than arr[n-1], and max ending with arr[n-1] needs  // to be updated, then update it  for (int i = 1; i < n; i++) {  res = _lis(arr, i);  if (arr[i - 1] < arr[n - 1]  && res + 1>max_ending_here) max_ending_here = res + 1;  } // Comparez max_ending_here avec le max global. Et // met à jour le maximum global si nécessaire if (max_ref< max_ending_here)  max_ref = max_ending_here;  // Return length of LIS ending with arr[n-1]  return max_ending_here;  }  // The wrapper function for _lis()  static int lis(int arr[], int n)  {  // The max variable holds the result  max_ref = 1;  // The function _lis() stores its result in max  _lis(arr, n);  // Returns max  return max_ref;  }  // Driver program to test above functions  public static void main(String args[])  {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = arr.length;  // Function call  System.out.println('Length of lis is '  + lis(arr, n));  } } // This code is contributed by Rajat Mishra>

# A naive Python implementation of LIS problem # Global variable to store the maximum global maximum # To make use of recursive calls, this function must return # two things: # 1) Length of LIS ending with element arr[n-1]. We use # max_ending_here for this purpose # 2) Overall maximum as the LIS may end with an element # before arr[n-1] max_ref is used this purpose. # The value of LIS of full array of size n is stored in # *max_ref which is our final result def _lis(arr, n): # To allow the access of global variable global maximum # Base Case if n == 1: return 1 # maxEndingHere is the length of LIS ending with arr[n-1] maxEndingHere = 1 # Recursively get all LIS ending with # arr[0], arr[1]..arr[n-2] # If arr[i-1] is smaller than arr[n-1], and # max ending with arr[n-1] needs to be updated, # then update it for i in range(1, n): res = _lis(arr, i) if arr[i-1] < arr[n-1] and res+1>maxEndingHere : maxEndingHere = res + 1 # Comparez maxEndingHere avec le maximum global. Et # mettre à jour le maximum global si nécessaire maximum = max(maximum, maxEndingHere) return maxEndingHere def lis(arr): # Pour permettre l'accès à la variable globale global maximum # Longueur de l'arr n = len(arr) # La variable maximum contient le résultat maximum = 1 # La fonction _lis() stocke son résultat dans maximum _lis(arr, n) return maximum # Programme pilote pour tester la fonction ci-dessus si __name__ == '__main__' : arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # Appel de fonction print('Length of lis is', lis(arr)) # Ce code est fourni par NIKHIL KUMAR SINGH>

using System; // A Naive C# Program for LIS Implementation class LIS {  // Stores the LIS  static int max_ref;  // To make use of recursive calls, this function must  // return two things: 1) Length of LIS ending with  // element arr[n-1]. We use max_ending_here for this  // purpose 2) Overall maximum as the LIS may end with an  // element before arr[n-1] max_ref is used this purpose.  // The value of LIS of full array of size n is stored in  // *max_ref which is our final result  static int _lis(int[] arr, int n)  {  // Base case  if (n == 1)  return 1;  // 'max_ending_here' is length of LIS ending with  // arr[n-1]  int res, max_ending_here = 1;  // Recursively get all LIS ending with arr[0],  // arr[1] ... arr[n-2]. If arr[i-1] is smaller  // than arr[n-1], and max ending with arr[n-1] needs  // to be updated, then update it  for (int i = 1; i < n; i++) {  res = _lis(arr, i);  if (arr[i - 1] < arr[n - 1]  && res + 1>max_ending_here) max_ending_here = res + 1;  } // Comparez max_ending_here avec le maximum global // et mettez à jour le maximum global si nécessaire if (max_ref< max_ending_here)  max_ref = max_ending_here;  // Return length of LIS ending with arr[n-1]  return max_ending_here;  }  // The wrapper function for _lis()  static int lis(int[] arr, int n)  {  // The max variable holds the result  max_ref = 1;  // The function _lis() stores its result in max  _lis(arr, n);  // Returns max  return max_ref;  }  // Driver program to test above functions  public static void Main()  {  int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = arr.Length;  // Function call  Console.Write('Length of lis is ' + lis(arr, n)  + '
');  } }>

>

// C++ code of memoization approach for LIS #include  using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int f(int idx, int prev_idx, int n, int a[],  vector>& dp) { if (idx == n) { return 0;  } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1];  } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);  int prendre = INT_MIN;  if (prev_idx == -1 || a[idx]> a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][prev_idx + 1] = max(take, notTake); } // Fonction pour trouver la longueur de // la sous-séquence croissante la plus longue int longestSubsequence(int n, int a[]) { vector> dp(n + 1, vecteur (n + 1, -1));  return f(0, -1, n, a, dp); } // Programme pilote pour tester la fonction ci-dessus int main() { int a[] = { 3, 10, 2, 1, 20 };  int n = taillede(a) / taillede(a[0]);  // Appel de fonction cout<< 'Length of lis is ' << longestSubsequence(n, a);  return 0; }>

// A Memoization Java Program for LIS Implementation import java.lang.*; import java.util.Arrays; class LIS {  // To make use of recursive calls, this function must  // return two things: 1) Length of LIS ending with  // element arr[n-1]. We use max_ending_here for this  // purpose 2) Overall maximum as the LIS may end with an  // element before arr[n-1] max_ref is used this purpose.  // The value of LIS of full array of size n is stored in  // *max_ref which is our final result  static int f(int idx, int prev_idx, int n, int a[],  int[][] dp)  {  if (idx == n) {  return 0;  }  if (dp[idx][prev_idx + 1] != -1) {  return dp[idx][prev_idx + 1];  }  int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);  int take = Integer.MIN_VALUE;  if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][prev_idx + 1] = Math.max(take, notTake);  } // La fonction wrapper pour _lis() static int lis(int arr[], int n) { // La fonction _lis() stocke son résultat dans max int dp[][] = new int[n + 1][ n + 1] ;  for (int row[] : dp) Arrays.fill(row, -1);  return f(0, -1, n, arr, dp);  } // Programme pilote pour tester les fonctions ci-dessus public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 };  int n = a.longueur;  // Appel de fonction System.out.println('La longueur de lis est ' + lis(a, n));  } } // Ce code est fourni par Sanskar.>

# A Naive Python recursive implementation # of LIS problem import sys # To make use of recursive calls, this # function must return two things: # 1) Length of LIS ending with element arr[n-1]. # We use max_ending_here for this purpose # 2) Overall maximum as the LIS may end with # an element before arr[n-1] max_ref is # used this purpose. # The value of LIS of full array of size n # is stored in *max_ref which is our final result def f(idx, prev_idx, n, a, dp): if (idx == n): return 0 if (dp[idx][prev_idx + 1] != -1): return dp[idx][prev_idx + 1] notTake = 0 + f(idx + 1, prev_idx, n, a, dp) take = -sys.maxsize - 1 if (prev_idx == -1 or a[idx]>a[prev_idx]) : prendre = 1 + f(idx + 1, idx, n, a, dp) dp[idx][prev_idx + 1] = max(take, notTake) return dp[idx][prev_idx + 1] # Fonction pour trouver la longueur de la sous-séquence croissante # la plus longue. def longestSubsequence(n, a): dp = [[-1 for i in range(n + 1)]for j in range(n + 1)] return f(0, -1, n, a, dp) # Pilote programme pour tester la fonction ci-dessus si __name__ == '__main__' : a = [3, 10, 2, 1, 20] n = len(a) # Appel de fonction print('Length of lis is', longestSubsequence( n, a)) # Ce code est contribué par shinjanpatra>

// C# approach to implementation the memoization approach using System; class GFG {  // To make use of recursive calls, this  // function must return two things:  // 1) Length of LIS ending with element arr[n-1].  // We use max_ending_here for this purpose  // 2) Overall maximum as the LIS may end with  // an element before arr[n-1] max_ref is  // used this purpose.  // The value of LIS of full array of size n  // is stored in *max_ref which is our final result  public static int INT_MIN = -2147483648;  public static int f(int idx, int prev_idx, int n,  int[] a, int[, ] dp)  {  if (idx == n) {  return 0;  }  if (dp[idx, prev_idx + 1] != -1) {  return dp[idx, prev_idx + 1];  }  int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);  int take = INT_MIN;  if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx, prev_idx + 1] = Math.Max(take, notTake);  } // Fonction pour trouver la longueur de la sous-séquence // croissante la plus longue.  public static int longestSubsequence(int n, int[] a) { int[, ] dp = new int[n + 1, n + 1];  pour (int je = 0; je< n + 1; i++) {  for (int j = 0; j < n + 1; j++) {  dp[i, j] = -1;  }  }  return f(0, -1, n, a, dp);  }  // Driver code  static void Main()  {  int[] a = { 3, 10, 2, 1, 20 };  int n = a.Length;  Console.WriteLine('Length of lis is '  + longestSubsequence(n, a));  } } // The code is contributed by Nidhi goel.>

/* A Naive Javascript recursive implementation  of LIS problem */  /* To make use of recursive calls, this  function must return two things:  1) Length of LIS ending with element arr[n-1].  We use max_ending_here for this purpose  2) Overall maximum as the LIS may end with  an element before arr[n-1] max_ref is  used this purpose.  The value of LIS of full array of size n  is stored in *max_ref which is our final result  */  function f(idx, prev_idx, n, a, dp) {  if (idx == n) {  return 0;  }  if (dp[idx][prev_idx + 1] != -1) {  return dp[idx][prev_idx + 1];  }  var notTake = 0 + f(idx + 1, prev_idx, n, a, dp);  var take = Number.MIN_VALUE;  if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return (dp[idx][prev_idx + 1] = Math.max(take, notTake));  } // Fonction pour trouver la longueur de la sous-séquence // croissante la plus longue.  function longestSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1));  return f(0, -1, n, a, dp);  } /* Programme pilote pour tester la fonction ci-dessus */ var a = [3, 10, 2, 1, 20];  variable n = 5 ;  console.log('La longueur de lis est ' + longestSubsequence(n, a));    // Ce code est contribué par satwiksuman.>

// Dynamic Programming C++ implementation // of LIS problem #include  using namespace std; // lis() returns the length of the longest // increasing subsequence in arr[] of size n int lis(int arr[], int n) {  int lis[n];  lis[0] = 1;  // Compute optimized LIS values in  // bottom up manner  for (int i = 1; i < n; i++) {  lis[i] = 1;  for (int j = 0; j < i; j++)  if (arr[i]>arr[j] && lis[i]< lis[j] + 1)  lis[i] = lis[j] + 1;  }  // Return maximum value in lis[]  return *max_element(lis, lis + n); } // Driver program to test above function int main() {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function call  printf('Length of lis is %d
', lis(arr, n));  return 0; }>

// Dynamic Programming Java implementation // of LIS problem import java.lang.*; class LIS {  // lis() returns the length of the longest  // increasing subsequence in arr[] of size n  static int lis(int arr[], int n)  {  int lis[] = new int[n];  int i, j, max = 0;  // Initialize LIS values for all indexes  for (i = 0; i < n; i++)  lis[i] = 1;  // Compute optimized LIS values in  // bottom up manner  for (i = 1; i < n; i++)  for (j = 0; j < i; j++)  if (arr[i]>arr[j] && lis[i]< lis[j] + 1)  lis[i] = lis[j] + 1;  // Pick maximum of all LIS values  for (i = 0; i < n; i++)  if (max < lis[i])  max = lis[i];  return max;  }  // Driver code  public static void main(String args[])  {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = arr.length;  // Function call  System.out.println('Length of lis is '  + lis(arr, n));  } } // This code is contributed by Rajat Mishra>

# Dynamic programming Python implementation # of LIS problem # lis returns length of the longest # increasing subsequence in arr of size n def lis(arr): n = len(arr) # Declare the list (array) for LIS and # initialize LIS values for all indexes lis = [1]*n # Compute optimized LIS values in bottom up manner for i in range(1, n): for j in range(0, i): if arr[i]>arr[j] et lis[i]< lis[j] + 1: lis[i] = lis[j]+1 # Initialize maximum to 0 to get # the maximum of all LIS maximum = 0 # Pick maximum of all LIS values for i in range(n): maximum = max(maximum, lis[i]) return maximum # Driver program to test above function if __name__ == '__main__': arr = [10, 22, 9, 33, 21, 50, 41, 60] print('Length of lis is', lis(arr)) # This code is contributed by Nikhil Kumar Singh>

// Dynamic Programming C# implementation of LIS problem using System; class LIS {  // lis() returns the length of the longest increasing  // subsequence in arr[] of size n  static int lis(int[] arr, int n)  {  int[] lis = new int[n];  int i, j, max = 0;  // Initialize LIS values for all indexes  for (i = 0; i < n; i++)  lis[i] = 1;  // Compute optimized LIS values in bottom up manner  for (i = 1; i < n; i++)  for (j = 0; j < i; j++)  if (arr[i]>arr[j] && lis[i]< lis[j] + 1)  lis[i] = lis[j] + 1;  // Pick maximum of all LIS values  for (i = 0; i < n; i++)  if (max < lis[i])  max = lis[i];  return max;  }  // Driver code  public static void Main()  {  int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = arr.Length;  // Function call  Console.WriteLine('Length of lis is '  + lis(arr, n));  } } // This code is contributed by Ryuga>

>