class Solution { public: 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; } };
另外若要輸出所找到的最長遞增子序列的話,請參考底下作法:
/* Longest Increasing Subsequence */ #include <iostream> #include <algorithm> #include <vector> using namespace std; int main( void ) { vector<int> num; int input; short *best; while( cin >> input ) { num.push_back( input ); } best = new short[ num.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 < num.size(); i++ ) { short tempBest = 0; //找出比數字比 num[i] 小且序列長度為最大的值 for( int k = i - 1; k >= 0; k-- ) { if( num[i] > num[k] ) { if( tempBest < best[k] ) { tempBest = best[k]; } } } best[i] = tempBest + 1; if( best[i] > maxLen ) maxLen = best[i]; } vector<int>* subSet = new vector<int>[ maxLen ]; for( int i = 0; i < num.size(); i++ ) { //cout << best[i] << " "; subSet[ best[i] - 1].push_back( num[i] ); } cout << endl << endl; for( int i = 0; i + 1 < maxLen; i++ ) { sort( subSet[i].begin(), subSet[i].end() ); int max = 0; for( int j = 0; j < subSet[i].size(); j++ ) if( (subSet[i])[j] < (subSet[i+1])[subSet[i+1].size() - 1] && max < (subSet[i])[j]) { max = (subSet[i])[j]; } cout << max << " "; } cout << (subSet[maxLen - 1])[0] << endl; delete[] best; delete[] subSet; return 0; }
沒有留言:
張貼留言