最大増加サブ

Question

次のように問題がある：必ずしも明確ではないn個の整数の配列Lが与えられると 、最大長の増加シーケンスを計算するアルゴリズムを記述：

Iが開発漸化式でありますこの：

私は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 

これらの要素に、次に最大：この典型的な問題のために使用される標準的な解決策は、すなわち、第一の配列のすべての要素のためのLiで終わる最大増加シーケンスを計算し、これらの値の最大であります。

私はあなたが私のソリューションがとにかくあったと思っているかどうかを知りたかったのです。

Answer 1

ここにヒントがあります：アルゴリズムで保持しようとするループ不変量は、変数k =最長増加サブシーケンスの先頭のインデックスです。したがって、整数のシーケンス[0 ... n]を反復すると、それに応じてkの値が増加します。

Answer 2

// Integersの配列が与えられている場合、最長増加サブシーケンスの長さを見つけてシーケンスを出力します。

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


}