SUBSEQUENCE

• Problem Description

  
  "Finding the longest increasing subsequence is an old and well-known problem now. Here you will have to do something similar. You need to find the longest weird subsequence (LWS) of the given string. The subsequence is called weird if it can be split into two disjoint subsequences, one of which is non-decreasing and the other one is non-increasing. 
  Just for clarity, by subsequence of the given string S we mean any string that can be obtained from S by erasing from it zero or more characters. So empty string is a subsequence of any string and any string is a subsequence of itself. Further, note that we consider only strings composed of lowercase Latin letters and these letters compared by their ASCII codes. So, for example, 'a' is smaller than 'b' and 'p' is larger than 'h'. 
  Now let's consider some example. Let S=""aabcazcczba"". Then ""abczz"" is its some non-decreasing subsequene, ""zccb"" is its some non-increasing subsequence and ""aabczcczba"" is its some weird subsequence since it can be split into non-decreasing subsequence ""aabzz"" and non-increasing subsequence ""cccba"": ""AABcZccZba"" (first subsequence is shown by capital letters just for calrity). 
  Input
  The first line contains a single positive integer T, the number of test cases. T test cases follow. The only line of each test case contains a non-empty string S composed of lowercase Latin letters. 
  Output
  For every test case, output the length of the LWS of the given string. 
  "

• CODING ARENA::

• #include<stdio.h>

  #include<string.h>

  int main()

  {

   int t;

   scanf("%d",&t);

   while(t--)

   {

    char s[2005];

    int a[26][26];

    int i,j;

     for(i=0;i<26;i++)

       for(j=0;j<26;j++)

         a[i][j]=0; 

    scanf("%s",s); 

    int k,max;

    int len=strlen(s); 

    int first[26]={0};

    int second[26]={0}; 

    for(i=0;i<len;i++)

    {

  int x=s[i]-'a'; 

  for(k=0;k<26;k++)

  {

    max=-1; 

    for(j=0;j<=x;j++)

  if(a[j][k]>max)

  max=a[j][k]; 

    first[k]=max+1;

  } 

  for(j=0;j<26;j++)

  {

  max=-1; 

  for(k=25;k>=x;k--)

  if(a[j][k]>max)

    max=a[j][k]; 

  second[j]=max+1;

  }

  for(j=0;j<26;j++)

    a[x][j]=first[j]; 

  for(j=0;j<26;j++)

    a[j][x]=second[j]; 

  }

  
  

    int ans=-1; 

    for(i=0;i<26;i++)

  for(j=0;j<26;j++)

  if(a[i][j]>ans)

    ans=a[i][j];

   

   printf("%d\n",ans);

  }

  return 0;

  } 

• Test Case 1

  
  Input (stdin)

  3
  
  abc
  
  cbazyzabc
  
  ddaabbaacc
  
  

  Expected Output

  3
  
  6
  
  10

• Test Case 2

  
  Input (stdin)

  1
  
  hadsadchgs
  
  

  Expected Output

  8