算法1：求得一个字符串的最大增长序列（O（n^2））

算法1：求得一个字符串的最大增长序列（O（n^2））

思路：将该序列按照升序的方式进行排列， 将升序的字符串中相同的字符去掉，与该序列求公共子序列
最长公共子序列：红色代码标注
                       该问题具有最优子结构性质，从后向前考虑
                       若X={x1, x2, x3, x4,xn}和Y={y1,y2,y3,y4,yn}的最长公共子序列为Z={z1,z2,z3,z4,zn};
                  则：1》若 xm=yn,则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列
                         2》若 xm！=yn,则xm！=zk,且Z是Xm-1和Y的最长公共子序列
                         3》若 xm！=yn,则zk  !=yn,且Z是Yn-1和Y的最长公共子序列
                    用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。
                                  
                                   0                                    i=0,j=0
            c[i][j]           c[i-1][j-1]+1                    i,j>0;xi=yj
                              max{ c[i][j-1] ,c[i-1][j] }    i,j>0 ; xi!=yj
代码实现：                        

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20
//按照冒泡排序的方法将字符串进行排序
void sort_maopao(char *mes);
void show(int cst[][MAX],int hang , int lie);
void LCS( int l1,int l2 , int bs[][MAX],char * mes);
void LCSLength(char * mes1,int l1, char *mes2,int l2,int cst[][MAX],int bs[][MAX]);
void delete_same_char(char mes2[], int len);
int main()
{

    char *mes1 = (char*)malloc(MAX*sizeof(char));
    char *mes2 = (char*)malloc(MAX*sizeof(char));
    int  c[MAX][MAX]={0},bs[MAX][MAX]={0};

    printf("please input the string :");
    fgets(mes1,MAX,stdin);
    strcpy(mes2,mes1);
    sort_maopao(mes2);
    delete_same_char(mes2,strlen(mes2));
    printf("%s \n",mes2);
    LCSLength(mes1,strlen(mes1),mes2,strlen(mes2),c,bs);
    show(c,strlen(mes1),strlen(mes2));
    show(bs,strlen(mes1),strlen(mes2));
    LCS( strlen(mes1),strlen(mes2),bs,mes1);
    printf("\n");
    return 0;
}
void sort_maopao(char *mes)
{
    int  i=0,j=0;
    char c;

    for(i=0;i<strlen(mes);i++)
        for(j=0;j<strlen(mes)-i-1;j++)
            if(mes[j]>=mes[j+1])
            {
                c = mes[j];
                mes[j]=mes[j+1];
                mes[j+1]=c;
            }

    printf("%s",mes);
}
void delete_same_char(char mes2[], int len)
{
    char mes[MAX];
    int in,ik=-1;

    memcpy(mes,mes2,len);
    memset(mes2,0,MAX);
    for(in=0;in<len;in++)
        if(in==0 || mes[in]!=mes2[ik])
            mes2[++ik]=mes[in];

}
void show(int cst[][MAX], int col,int lie)
{
    int in= 0,ij=0;

    printf("&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&\n");
    for(in=1;in<=col;in++) {
        for(ij=1;ij<=lie;ij++)
            printf(" %d ",cst[in][ij]);
        printf("\n");
    }

}
void LCS(int l1, int l2, int bs[][MAX],char *res)
{
    if(l1==0 ||l2 ==0)
        return ;
    if(bs[l1][l2]==1)
    {
        LCS(l1-1,l2-1,bs,res);
        printf("%c",res[l1-1]);
    } else if(bs[l1][l2]==2)
        LCS(l1,l2-1,bs,res);
    else
        LCS(l1-1,l2,bs,res);
}
void LCSLength(char *mes1, int l1, char *mes2, int l2, int cst[][MAX],int bs[][MAX])
{
    int   in=0,ij=0;

    for(in=1;in<=l1;in++)
        cst[in][0]=0;
    for(in=1;in<=l2;in++)
        cst[0][in]=0;

    for(in=0;in<=l1;in++)
        for(ij=0;ij<=l2;ij++) {
            if(mes1[in]==mes2[ij]) {
                cst[in+1][ij+1]=cst[in][ij]+1;
                bs[in+1][ij+1]=1;
            }
            else if(cst[in+1][ij]>=cst[in][ij+1])
            {
                cst[in+1][ij+1]=cst[in+1][ij];
                bs[in+1][ij+1]=2;
            }
            else {

                cst[in+1][ij+1]=cst[in][ij+1];
                bs[in+1][ij+1]=3;
            }
        }
}