台中女中程式解題系統：b032: 持續進步獎

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b032。
此題用 Dynamic Programming ，可參考 https://leetcode.com/articles/longest-increasing-subsequence/ 的 Approach 3: Dynamic Programming 小節；或是演算法筆記的Longest Increasing Subsequence: Dynamic Programming

演算法

先求出第0項到第n項的 LIS 長度 length(n)：

再找出 { length(i), for 0 <= i <= n }中的最大值。

程式碼：

1. #include <iostream>  
2. #include <cstring>  
3. #include <vector>  
4.   
5. using namespace std;  
6.   
7. int lengthOfLIS(vector<int>& nums) {  
8.     if( nums.size() == 0 ) return 0;  
9.   
10.     short *best;  
11.     best = new short[ nums.size() ];  
12.   
13.     best[0] = 1;  
14.   
15.     short maxLen = 1;  
16.   
17.     // Dynamic Programming:  
18.     // if( num[i] > num[k] )  
19.     //   best[i] = max(best[0] ... best[k])  
20.     for( int i = 1; i < nums.size(); i++ )  
21.     {  
22.         short tempBest = 0;  
23.   
24.         //找出比數字比 num[i] 小且序列長度為最大的值  
25.         for( int k = i - 1; k >= 0; k-- )  
26.         {  
27.             if( nums[i] > nums[k] )  
28.             {  
29.                 if( tempBest < best[k] )  
30.                 {  
31.                     tempBest = best[k];  
32.                 }  
33.             }  
34.         }  
35.   
36.         best[i] = tempBest + 1;  
37.         if( best[i] > maxLen ) maxLen = best[i];  
38.     }  
39.   
40.     delete[] best;  
41.     return maxLen;  
42. }  
43.   
44. int main()  
45. {  
46.     int n;  
47.     cin >> n;  
48.   
49.     int num[n];  
50.   
51.     for(int i = 0; i < n; i++)  
52.     {  
53.         cin >> num[i];  
54.     }  
55.   
56.     vector<int> tmp(num, num + n);  
57.   
58.     cout << lengthOfLIS(tmp);  
59.     return 0;  
60. }