最大遞增子

Question

的問題是如下： 給定n個整數的序列L不一定明顯，寫，計算最大長度的遞增子的算法：

我開發的遞歸方程是這樣的：

我從0開始的索引：

If j = n opt(j) = 0 (base case) 
otherwise opt(j) = max j <i <= n such that Lj <Li = {opt(i) +1} 

你認爲是正確的，這樣做呢？用於這一典型問題的標準解決方法是先計算在李的最大遞增子的結局對序列的所有元素，然後這些值的最大值，即：

if i = 1 opt (i) = 1 
otherwise opt (i) = max 1 <= j <= i-1 and Lj <Li = {opt (i)} +1 

，然後在這些元素的最大值。

所以我想知道你是否認爲我的解決方案正確無論如何。

Answer 1

這裏有個提示：在算法中試圖保留的循環不變量是一個變量，k =最長增加子序列開始處的索引。因此，當你迭代整數序列[0 ... n]時，相應地增加k值。

Answer 2

//給定一個整型數組，找到最長增加子序列的長度並打印序列。

int longsub (int a[], int len) { 

    int localsum = 0; 
    int i = 0; 
    int begin = i; 
    int localsublen = 1; 
    int globalsunlen = 0; 
    int end = i; 

    for (i=1; i< len; i++) { 

     if (a[i] > a[i-1]) { 
       localsublen++; 
     } 
     else { 
      newbegin = i; 
      localsublen = 1; 
     } 

     if (localsublen > globalsublen) { 
      begin = newbegin; 
      end = i; 
      globalsublen = localsublen; 
     } 
    } 

    for (i=begin;i <= end; i++)  
     printf ("%d.\n",a[i]); 


}