最長増加部分列、動的計画法

Question

I次のような問題があります。

が所定の配列/配列の最長増加部分列を検索します。

つまり、サブシーケンスの 要素が厳密に昇順であり、サブシーケンスができるだけ長い配列のサブシーケンスを見つけます。このサブシーケンスは、必ずしも連続していないか、または一意ではない ではありません。この場合、最も長くなるサブシーケンスの長さは だけです。

例：

入力：[0、8、4、12、2、10、6、14、1、9、5、13、3、11、7、15]出力 ：6配列：[0、2、6、9、13、15]又は[0、4、6、9、11、15]または[0、 4、6、9、13、15]

これはDPの問題です。私は暗記の段階で問題があります。 はここに私のコードです：これは場所に一度私に間違った結果を与えている理由私は正しい結果を持っている場所でのメモのHashMapなし

public int lis(final List<Integer> a) { 
    return maxIncreasing(0, Integer.MIN_VALUE, a); 
} 
HashMap<Integer, Integer> memo = new HashMap<>(); 
private int maxIncreasing(int index, int lastElt, final List<Integer> a) { 
    if(memo.containsKey(index)) return memo.get(index); 
    // end? 
    if(index >= a.size()) return 0; 
    int weTake = Integer.MIN_VALUE; 
    // can we take it? 
    if(a.get(index) > lastElt) { 
     // take it or don't 
     weTake = maxIncreasing(index + 1, a.get(index), a) + 1; 
    } 
    int weDoNot = maxIncreasing(index + 1, lastElt, a); 
    int max = Math.max(weTake, weDoNot); 
    memo.put(index, max); 
    return max; 
} 

、私はわかりません。

ありがとうございました。あなたはlastEltの世話をされていないためである

Answer 1

。基本的には、には、lastEltの値に応じて複数のソリューションを用意することができます。そのため、あなたはindexとlastEltの両方が含まれているあなたのためのmemoKeyを持っている必要があります。しかし、おそらくまだ再帰はメモリのオーバーヘッドを引き起こしている、賢明な私にいくつかの問題のパフォーマンスを与えて、このソリューションが有効である

class Key { 
     final int index; 
     final int lastEl; 

     Key(int index, int lastEl) { 
      this.index = index; 
      this.lastEl = lastEl; 
     } 

     @Override 
     public boolean equals(Object o) { 
      if (this == o) return true; 
      if (o == null || getClass() != o.getClass()) return false; 

      Key key = (Key) o; 

      if (index != key.index) return false; 
      return lastEl == key.lastEl; 

     } 

     @Override 
     public int hashCode() { 
      int result = index; 
      result = 31 * result + lastEl; 
      return result; 
     } 
    } 

    public int lis(final List<Integer> a) { 
     return maxIncreasing(0, Integer.MIN_VALUE, a); 
    } 
    HashMap<Key, Integer> memo = new HashMap<>(); 
    private int maxIncreasing(int index, int lastElt, final List<Integer> a) { 
     Key key = new Key(index ,lastElt); 
     if(memo.containsKey(key)) return memo.get(key); 
     // end? 
     if(index >= a.size()) return 0; 
     int weTake = Integer.MIN_VALUE; 
     // can we take it? 
     if(a.get(index) > lastElt) { 
      // take it or don't 
      weTake = maxIncreasing(index + 1, a.get(index), a) + 1; 
     } 
     int weDoNot = maxIncreasing(index + 1, lastElt, a); 
     int max = Math.max(weTake, weDoNot); 
     memo.put(key, max); 
     return max; 
    }