Problem description
?
某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。

Input
輸入數據為導彈依次飛來的高度，所有高度值均為不大于30000的正整數。

Output
輸出只有一行是這套系統最多能攔截的導彈數和要攔截所有導彈最少要配備這種導彈攔截系統的套數。兩個數據之間用一個空格隔開.

Sample Input
389 207 155 300 299 170 158 65
?
Sample Output
6 2


第一問顯然是求最長不下降序列長度
第二問求最長上升序列長度

?1 #include? < iostream >
?2 #include? < vector >
?3
?4 using ? namespace ?std;
?5
?6 int ?main()
?7 {
?8 ????vector < int > ??a;
?9 ???? int ????data;
10
11 ???? while ?(?cin? >> ?data?)
12 ????????a.push_back(?data?);
13
14 ???? int ???len = ?static_cast < int > (?a.size?()?);
15 ???? int * ??value = ? new ? int [len];
16 ???? int ???max,?t = ? 0 ;
17
18 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
19 ????????value[i] = ? 1 ;
20
21 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
22 ???? {
23 ????????max = ? 0 ;
24 ????????t = ? 0 ;
25
26 ???????? for ?(? int ?j = ? 0 ;?j < ?i;? ++ j?)
27 ???????????? if ?(?a[i] < ?a[j]? && ?value[j] > ?max?)
28 ???????????? {
29 ????????????????t = ? 1 ;
30 ????????????????max = ?value[j];
31 ????????????}
32
33 ???????? if ?(?t != ? 0 ?)
34 ????????????value[i] = ?max + ? 1 ;
35 ????}
36
37 ????max = ? 1 ;
38 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
39 ???????? if ?(?value[i] > ?max?)
40 ????????????max = ?value[i];
41
42 ????cout? << ?max;
43
44 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
45 ????????value[i] = ? 1 ;
46
47 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
48 ???? {
49 ????????max = ? 0 ;
50 ????????t = ? 0 ;
51
52 ???????? for ?(? int ?j = ? 0 ;?j < ?i;? ++ j?)
53 ???????????? if ?(?a[i] > ?a[j]? && ?value[j] > ?max?)
54 ???????????? {
55 ????????????????t = ? 1 ;
56 ????????????????max = ?value[j];
57 ????????????}
58
59 ???????? if ?(?t != ? 0 ?)
60 ????????????value[i] = ?max + ? 1 ;
61 ????}
62
63 ????max = ? 1 ;
64 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
65 ???????? if ?(?value[i] > ?max?)
66 ????????????max = ?value[i];
67
68 ????cout? << ? ' ? ' ? << ?max;
69
70 ???? return ? 0 ;
71 }
72