網頁

2014年3月19日 星期三

POJ 2533 Longest Orderded Subsequence

Longest Increasing Sub-sequence(LIS)題目
想法:
    這裡提供兩種方法:

  1. 把已經讀入的數字存起來,每次讀一個新的數字i的時候,就把LIS[i]設成1,然後把現在這個新數字i與以前已經讀入的數字j做比較,如果i比j大且LIS[i]<LIS[j]+1,就把LIS[i]=LIS[j]+1。最後輸出最大的LIS值即可。
  2. 與上面不同,LIS[]是存讀入的數字,一開始LIS[]是空的,慢慢放數字,每次讀入一個新的數字,從i=0,如果該數字>LIS[i],就讓i++,直到在LIS表裡上不去為止,然後看該數字是否比LIS[i]小,如果是則更新LIS[i]的値。