c语言求最长递增(减)子序列

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

typedef short (*cmpfun)(int, int);

short max(int a, int b)
{
    return a > b;
}

short min(int a, int b)
{
    return a < b;
}

/*最长递增(减)子序列*/
int getdp(int *a, int n, cmpfun f, int *dp, int *s)
{
    int **lis = malloc(n*sizeof(int *));
    int cnt;
    int ans = 1;
    int m = 0;
    int d;
    int i, j;

    memset(dp, 0x00, n*sizeof(int));

    lis[0] = malloc(sizeof(int));
    dp[0] = 1;
    lis[0][0] = a[0];

    for(i=1; i<n; i++)
    {
        cnt = 1;

        for(j=0; j<i; j++)
        {
            if(f(a[i], a[j]))
            {
                if(dp[j]+1 > cnt)
                {
                    cnt = dp[j]+1;
                }
            }
        }

        dp[i] = cnt;
    }

    for(i=1; i<n; i++)
    {
        lis[i] = malloc(dp[i]*sizeof(int));

        if(dp[i] > ans)
        {
            m = i;
            ans = dp[i];
        }
    }

    for(i=0; i<n; i++)
    {
        cnt = 1;
        d = -1;

        for(j=0; j<i; j++)
        {
            if(f(a[i], a[j]))
            {
                if(dp[j]+1 > cnt)
                {
                    cnt = dp[j]+1;
                    d = j;
                }
            }
        }

        if(d >= 0)
        {
            for(j=0; j<dp[d]; j++)
            {
                lis[i][j] = lis[d][j];
            }
        }
        else
        {
            j = 0;
        }

        lis[i][j] = a[i];
    }

    for(i=0; i<dp[m]; i++)
    {
        s[i] = lis[m][i];
    }

    for(i=1; i<n; i++)
    {
        free(lis[i]);
        lis[i] = NULL;
    }

    free(lis);
    lis = NULL;

    return ans;
}

int main()
{
    int a[3000];
    int b[3000];
    int c[3000];
    int d[3000];
    int n = 0;
    int s;
    int m[4];
    int i;

    while(scanf("%d", &n) != EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d", a+i);
        }
    
        m[0] = getdp(a, n, max, b, c);
        m[1] = getdp(a, n, min, b, d);

        printf("%d\n", m[0]);

        for(i=0; i<m[0]; i++)
        {
            printf("%d ", c[i]);
        }

        printf("\n");

        printf("%d\n", m[1]);

        for(i=0; i<m[1]; i++)
        {
            printf("%d ", d[i]);
        }
    
        printf("\n");
    }

    return 0;
}

2.编译源码

$ gcc -o example examle.c -std=c89

3.运行及其结果

$ ./example
8
186 186 150 200 160 130 197 200
4
150 160 197 200 
3
186 150 130