最大递增子

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]); 


}