Longest Increasing Subsequence Leetcode Code Example

Example 1: longest common subsequence

class Solution:     def longestCommonSubsequence(self, text1: str, text2: str) -> int:         """         text1: horizontally         text2: vertically         """         dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]                  for row in range(1, len(text2)+1):             for col in range(1, len(text1)+1):                 if text2[row-1]==text1[col-1]:                     dp[row][col] = 1+ dp[row-1][col-1]                 else:                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])         return dp[len(text2)][len(text1)]

Example 2: longest increasing subsequence when elements hae duplicates

#include <iostream> #include <algorithm> using namespace std;   // define maximum possible length of X and Y #define N 20   // lookup[i][j] stores the length of LCS of subarray X[0..i-1], Y[0..j-1] int lookup[N][N];   // Function to find LCS of array X[0..m-1] and Y[0..n-1] void LCS(int X[], int Y[], int m, int n) {     // return if we have reached the end of either array     if (m == 0 || n == 0)         return;       // if last element of X and Y matches     if (X[m - 1] == Y[n - 1])     {         LCS(X, Y, m - 1, n - 1);         cout << X[m - 1] << " ";         return;     }     // else when the last element of X and Y are different       if (lookup[m - 1][n] > lookup[m][n - 1])         LCS(X, Y, m - 1, n);     else         LCS(X, Y, m, n - 1); }   // Function to find length of Longest Common Subsequence of // array X[0..m-1] and Y[0..n-1] void findLCS(int X[], int Y[], int m, int n) {     // first row and first column of the lookup table     // are already 0 as lookup[][] is globally declared       // fill the lookup table in bottom-up manner     for (int i = 1; i <= m; i++)     {         for (int j = 1; j <= n; j++)         {             // if current element of X and Y matches             if (X[i - 1] == Y[j - 1])                 lookup[i][j] = lookup[i - 1][j - 1] + 1;               // else if current element of X and Y don't match             else                 lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);         }     }       // find longest common sequence     LCS(X, Y, m, n); }   // Function to remove duplicates from a sorted array int removeDuplicates(int X[], int n) {     int k = 0;     for (int i = 1; i < n; i++)         if (X[i] != X[k])             X[++k] = X[i];       // return length of sub-array containing all distinct characters     return k + 1; }   // Iterative function to find length of longest increasing subsequence (LIS) // of given array using longest common subsequence (LCS) void findLIS(int X[], int n) {     // create a copy of the original array     int Y[n];     for (int i = 0; i < n; i++)         Y[i] = X[i];       // sort the copy of the original array     sort(Y, Y + n);       // remove all the duplicates from Y     int m = removeDuplicates (Y, n);       // perform LCS of both     findLCS(X, Y, n, m); }   // Longest Increasing Subsequence using LCS int main() {     int X[] = { 100,1,100,1,100 };     int n = sizeof(X)/sizeof(X[0]);       cout << "The LIS is ";     findLIS(X, n);       return 0; }