子数列(类似最长升序列) boj1004

子数列Submit: 1148   Accepted:338Time Limit: 2000MS  Memory Limit: 65536KDescription
现 在有一个数列，需要你求得该数列满足下述要求的最长子数列。子数列要求：这个子数列可以被分成前后两个部分，且两部分共同拥有一个数列项（即前一部分的最 后一个数列项和后一部分的第一个数列项是同一个数列项）；子数列的前一部分各项要严格递增，后一部分各项要严格递减。例如，数列 1 4 6 5 2 1 可以分成 1 4 6 和 6 5 2 1 这两部分。他们都含有数列项 6 ，且前者各项严格递增，后者各项严格递减。


请你编写程序回答，对一个数列最少剔除几项，就可使剩下的各项组成的子数列满足上述的要求。

Input
输入数据有若干组。每组的第一行为整数 n (1 <= n <= 50) 表示数列的项数，第二行的 n 个整数即为该数列的各项，范围 1 到 1000000000 。

Output
输出最少需要剔除数列中的几项。一个结果一行。

Sample Input

6
1 4 6 5 2 1
5
2 2 2 2 2

Sample Output

0
4


解题思路：
转化成最长升序列的方法求解。
先求原始sequence的最长升序列数组。
然后再求反转sequence的最长升序列数组。
综合两个最长升序列数组，求得满足要求的最长的序列


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

int array[60], array_r[60], lis[60], lis_r[60];

void LIS(int size, int *seq, int *max_arr)
{
    int i, j;
    for (i=1 ; i<=size ; i++) /* 注意，设置最长升序列数组的初始值为1 */
        max_arr[i] = 1;
    
    for (i=2 ; i<=size ; i++)
    {
        for (j=1 ; j<i ; j++)
        {
            /* 若可以加长，则改变之 */
            if (seq[i] > seq[j] && max_arr[j] + 1 > max_arr[i])
                max_arr[i] = max_arr[j] + 1;
        }
    }
}

int find_max(int size, int *arr, int *arr_r)
{
    int i, max = 0;
    for (i=1 ; i<=size ; i++)
    {
        if (arr[i] + arr_r[size - i + 1] > max)
        {
            max = arr[i] + arr_r[size - i + 1];
        }
    }
    return max - 1;
}

int main(int argc, char *argv[])
{
    int n, i, max;
    while (EOF != scanf("%d", &n))
    {
        memset(lis, 0, sizeof(lis));
        memset(lis_r, 0, sizeof(lis_r));
        for (i=1 ; i<=n ; i++)
        {
            scanf("%d", &array[i]);
        }
        LIS(n, array, lis);
        /* 翻转原sequence，再求一遍最长升序列 */
        for (i=1 ; i<=n ; i++)
        {
            array_r[n - i + 1] = array[i];
        }
        LIS(n, array_r, lis_r);
        /* 找到满足条件的最长序列 */
        max = find_max(n, lis, lis_r);
        printf("%d\n", n - max);
    }
}