台中女中程式解題系統: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.     forint i = 1; i < nums.size(); i++ )  
  21.     {  
  22.         short tempBest = 0;  
  23.   
  24.         //找出比數字比 num[i] 小且序列長度為最大的值  
  25.         forint 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;  

沒有留言: