求數組中最長遞增子序列的解決方法

2020-01-26 16:04:48

字體：大中小

來源：轉載

供稿：網友

存儲擴展算法n2編程c 寫一個時間復雜度盡可能低的程序，求一個一維數組（N個元素）中的最長遞增子序列的長度。
例如：在序列1，-1，2，-3，4，-5，6，-7中，其最長的遞增子序列為1，2，4，6 或者 -1,2,4,6。（編程之美P198-202）
分析與解法
根據題目的要求，求一維數組中的最長遞增子序列，也就是找一個標號的序列b[0],b[1],…,b[m](0 <= b[0] < b[1] < … < b[m] < N)，使得array[b[0]]<array[b[1]]<…<array[b[m]]。

解法一
根據無后效性的定義我們知道，將各階段按照一定的次序排列好之后，對于某個給定的階段狀態來說，它以前各階段的狀態無法直接影響它未來的決策，而只能間接地通過當前的這個狀態來影響。換句話說，每個狀態都是歷史的一個完整總結。
同樣的，仍以序列1，-1，2，-3，4，-5，6，-7為例，我們在找到4之后，并不關心4之前的兩個值具體是怎樣，因為它對找到6沒有直接影響。因此，這個問題滿足無后效性，可以通過使用動態規劃來解決。
可以通過數字的規律來分析目標串：1，-1，2，-3，4，-5，6，-7。
使用i來表示當前遍歷的位置
當i=1時，顯然，最長的遞增序列為（1），序列長度為1.
當i=2是，由于-1<1。因此，必須丟棄第一個值后重新建立串。當前的遞增序列為（-1），長度為1。
當i=3時，由于2>1,2>-1。因此，最長的遞增序列為（1,2）,(-1,2),長度為2。在這里，2前面是1還是-1對求出后面的遞增序列沒有直接影響。（但是在其它情況下可能有影響）
依此類推之后，我們得出如下的結論。
假設在目標數組array[]的前i個元素中，最長遞增子序列的長度為LIS[i]。那么，
LIS[i+1]=max{1,LIS[k]+1}, array[i+1]>array[k], for any k <= i
即如果array[i+1]大于array[k],那么第i+1個元素可以接在LIS[k]長的子序列后面構成一個更長的子序列。于此同時array[i+1]本身至少可以構成一個長度為1的子序列。
根據上面的分析，就可以得到代碼清單：
C++代碼：

復制代碼代碼如下:

int Max(int *a, int n)
{
     int max = a[0];
     for(int i = 1; i < n; i++)
  if(max < a[i])
max = a[i];
     return max;
}
int LIS(vector<int> &array)
{
     int *a = new int[array.size()];
     for(int i = 0; i < array.size(); i++)
     {
 a[i] = 1;//初始化默認的長度
  for(int j = 0; j < i; j++)    //前面最長的序列
  {
     if(array [i] > array [j] && a[j] + 1 > a[i])   //當前數字比第j個大，且標記數組需要更新
{
     a[i] = a[j] + 1;
}
  }
     }
     return Max(a, array.size());
}

這種方法的時間復雜度為O(N2 + N) = O(N2)

解法二
在前面的分析中，當考察第i+1個元素的時候，我們是不考慮前面i個元素的分布情況的。現在我們從另一個角度分析，即當考察第i+1個元素的時候考慮前面i個元素的情況。
對于前面i個元素的任何一個遞增子序列，如果這個子序列的最大的元素比array[i+1]小，那么就可以將array[i+1]加在這個子序列后面，構成一個新的遞增子序列。
比如當i=4的時候，目標序列為1，-1，2，-3，4，-5，6，-7最長遞增序列為(1,2),(-1,2)。
那么，只要4>2,就可以把4直接增加到前面的子序列中形成一個新的遞增子序列。
因此，我們希望找到前i個元素中的一個遞增子序列，使得這個遞增子序列的最大的元素比array[i+1]小，且長度盡量地長。這樣將array[i+1]加在該遞增子序列后，便可以找到以array[i+1]為最大元素的最長遞增子序列。
仍然假設在數組的前i個元素中，以array[i]為最大元素的最長遞增子序列的長度為LIS[i]。
同時，假設：
長度為1的遞增子序列最大元素的最小值為MaxV[1];
長度為2的遞增子序列最大元素的最小值為MaxV[2];
……
長度為LIS[i]的遞增子序列最大元素的最小值為MaxV[LIS[i]];

本循環不變式P是：
P：k是序列a[0:i]的最長遞增子序列的長度，0≤i＜n。
容易看出，在由i-1到i的循環中，a[i]的值起關鍵作用。如果a[i]能擴展序列a[0;i-1]的最長遞增子序列的長度，則k=k+1，否則k不變。設a[0;i-1]中長度為k的最長遞增子序列的結尾元素是a[j](0≤j≤i-1)，則當a[i]≥a[j]時可以擴展，否則不能擴展。如果序列a[0;i-1]中有多個長度為k的最長遞增子序列，那么需要存儲哪些信息？容易看出，只要存儲序列a[0;i-1]中所有長度為k的遞增子序列中結尾元素的最小值b[k]。因此，需要將循環不變式P增強為：
P：0≤i＜n;k是序列a[0;i]的最長遞增子序列的長度；
b[k]是序列a[0;i]中所有長度為k的遞增子序列中最小結尾元素值。
相應地，歸納假設也增強為：已知計算序列a[0;i-1](i＜n)的最長遞增子序列的長度k以及序列a[0;i]中所有長度為k的遞增子序列中的最小結尾元素值b[k]的正確算法。
增強歸納假設后，在由i-1到i的循環中，當a[i]≥b[k]時，k=k+1，b[k]=a[i],否則k值不變。注意到當a[i]≥b[k]時，k值增加，b[k]的值為a[i]。那么，當a[i]＜b[k]時，b[l;k]的值應該如何改變？如果a[i]<b[l],則顯然應該將b[l]的只改變為a[i],當b[l]≤a[i]≤b[k]時，注意到數組b是有序的，可以用二分搜索算法找到下標j，使得b[j-1]≤a[i]≤b[j]。此時，b[1;j-1]和b[j+1;k]的值不變，b[j]的值改變為a[i]。

復制代碼代碼如下:

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &a)
{
  vector<int> b, p(a.size());//b是存儲遞增序列長度為k的最后元素下標 
 //比如b[1]是存儲遞增子序列最大元素的最小值的下標  
 //b是存儲最長子序列的下標 
  int u, v; 
  if (a.size() < 1) 
     return b;   
  b.push_back(0);
 for (int i = 1; i < (int)a.size(); i++)
 {    
    if (a[b.back()] < a[i])   
      { 
  p[i] = b.back();   
  b.push_back(i);   
  continue;      
     } 
     for (u = 0, v = b.size()-1; u < v;) //二分搜索 
    {   
      int c = (u + v) / 2;    
      if (a[b[c]] < a[i])  
      u=c+1;
      else v=c;    
    } 
    if (a[i] < a[b[u]]) 
    {     
     if (u > 0) 
p[i] = b[u-1];  
b[u] = i;    
    }  
} 
for (u = b.size(), v = b.back(); u--; v = p[v]) 
  b[u] = v;  
  return b;
}