新建 文本文档 (4).txt

所谓子序列

#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
long longest_sub(long num, long height[]);
int main(void)
{
    long data[MAX] = {0};
    long num = 0;
    long i;
    while (scanf("%d",&num) != EOF)
    {
        for (i=0; i<num; i++)
        {
            scanf("%d", data+i);
        }
        printf("%d\n", longest_sub(num,data));
    }
    return 0;
}
long longest_sub(long num, long height[])
{
    long begin = 0, end = num - 1;
    long index = 0;
    long *last = (long *)malloc(sizeof(long)*num);
    long length = 0;
    long maxLength = 0;
    
    for (; height[begin] >= height[begin+1]; begin++)
        ;
    for (; height[end] <= height[end-1]; end--)
        ;
    if (end <= begin)
    {
        return 1;
    }
    last[length] = height[begin];
    for (index = begin+1; index <= end; index++)
    {
        if (height[index] > last[maxLength])
        {
            last[++maxLength] = height[index];
        }
        
        else if (height[index] < last[0])
        {
            last[0] = height[index];
        }
        else
        {
            for (length = maxLength - 1; height[index] <= last[length]; length--)
                ;
            last[++length] = height[index];
        }
    }
    free(last);
    return maxLength + 1;
}