題目連結 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 }中的最大值。
程式碼:
- #include <iostream>
- #include <cstring>
- #include <vector>
- using namespace std;
- int lengthOfLIS(vector<int>& nums) {
- if( nums.size() == 0 ) return 0;
- short *best;
- best = new short[ nums.size() ];
- best[0] = 1;
- short maxLen = 1;
- // Dynamic Programming:
- // if( num[i] > num[k] )
- // best[i] = max(best[0] ... best[k])
- for( int i = 1; i < nums.size(); i++ )
- {
- short tempBest = 0;
- //找出比數字比 num[i] 小且序列長度為最大的值
- for( int k = i - 1; k >= 0; k-- )
- {
- if( nums[i] > nums[k] )
- {
- if( tempBest < best[k] )
- {
- tempBest = best[k];
- }
- }
- }
- best[i] = tempBest + 1;
- if( best[i] > maxLen ) maxLen = best[i];
- }
- delete[] best;
- return maxLen;
- }
- int main()
- {
- int n;
- cin >> n;
- int num[n];
- for(int i = 0; i < n; i++)
- {
- cin >> num[i];
- }
- vector<int> tmp(num, num + n);
- cout << lengthOfLIS(tmp);
- return 0;
- }
沒有留言:
張貼留言