最长上升子序列求方案C++代码

以下是最长上升子序列求方案的C代码：

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

int main()
{
    int n, i, j, max = 0, max_index = 0;
    scanf("%d", &n);
    int *a = (int*)malloc(n * sizeof(int));
    int *dp = (int*)malloc(n * sizeof(int));
    int *pre = (int*)malloc(n * sizeof(int));
    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        dp[i] = 1;
        pre[i] = -1;
        for(j = 0; j < i; j++)
        {
            if(a[j] < a[i] && dp[j] + 1 > dp[i])
            {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if(dp[i] > max)
        {
            max = dp[i];
            max_index = i;
        }
    }
    printf("%d\n", max);
    int *ans = (int*)malloc(max * sizeof(int));
    for(i = max - 1; i >= 0; i--)
    {
        ans[i] = a[max_index];
        max_index = pre[max_index];
    }
    for(i = 0; i < max; i++)
    {
        printf("%d ", ans[i]);
    }
    printf("\n");
    free(a);
    free(dp);
    free(pre);
    free(ans);
    return 0;
}

希望能对您有所帮助！