LeetCode OJ: 300. Longest Increasing Subsequence 最長遞增子序列

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

題目連結 https://leetcode.com/problems/longest-increasing-subsequence/，此題用動態規劃解。

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;
}