防御导弹 （C语言代码）

解题思路:

每一个数都可以有选与不选两种可能，一直递归到最后没有数可选的时候的长度就是最大长度，红色的数字就是最大长度的选择过程（不太会电脑画图，所以图没有画全）

注意事项：

1.opt(0)下面的  选与不选(左边选，右边不选)  指的是  是否选择第0个数字

2.如果选择了第n个数字，那么下一个选择的数字必须比第n个数字小

参考代码:

#include <stdio.h>

int opt(int *num,int n);

int x;

int main()

{

    int i,j,k,len;

    int num[10];

    x = 0;

    while(scanf("%d",&num[x++]) != EOF);

    len = opt(num,0);

    printf("%d\n",len);

    return 0;

}

int opt(int *num,int n)

{

    if(n < x)                     //只要n后面还有数就继续选择 

    {

        for(int i=n;i<x;i++)

        {

            if(num[n] > num[i]) return opt(num,i)+1;         //选择第n个数 

        }

        return opt(num,n+1);                                          //不选择第n个数 

    }

    else return 1; //如果没有数了就返回最小长度：1 

}