Write an efficient algorithm to find the maximum sorted subsequence in an input

Question

Write an efficient algorithm to find the maximum sorted subsequence in an input string. For instance, the maximum sorted subsequence in "zabacdefkabfhxy" is "abcdefkxy". The program should get input string from user and store it in an array. The program should then compute and print the maximum sorted subsequence.

Explanation / Answer

#include#include#define maxn 100100int max(int a,int b){return a>b?a:b;}int LongestCommonSubsequence(char S[],char T[]){int Slength = strlen(S);int Tlength = strlen(T);/* Starting the index from 1 for our convinience (avoids handling special cases for negative indices) */int iter,jter;for(iter=Slength;iter>=1;iter--){ S[iter] = S[iter-1];}for(iter=Tlength;iter>=1;iter--){ T[iter] = T[iter-1];}int common[Slength+1][Tlength+1];/* common[i][j] represents length of the longest common sequence in S[1..i], T[1..j] *//* Recurrence: common[i][j] = common[i-1][j-1] + 1 if S[i]==T[j] = max(common[i-1][j],common[i][j-1]) otherwise */ /*common[0][i]=0, for all i because there are no characters from string S*/for(iter=0;iter

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.