title: UVa 10134: Is Bigger Smarter? (Dynamic programming and longest increasing subsequence)
body: <pre><code>private void findLDS() {
      Integer[] array = Arrays.copyOf(elephants.iq, elephants.iq.length);
      Hashtable&lt;Integer, Integer&gt; eq = elephants.elephantiqs;
  
      Integer[] lds = new Integer[array.length];
      Integer[] prev= new Integer[array.length];
      lds[0] = 0;
      prev[0] = 0;
  
      int maxlds = 1, ending=0;
  
      for(int i = 0; i &lt; array.length; ++i) {
          lds[i] = 1;
          prev[i] = -1;
  
          for (int j = i; j &gt;= 0; --j) {
              if(lds[j] + 1 &gt; lds[i] &amp;&amp; array[j] &gt; array[i] &amp;&amp; eq.get(array[j]) &lt; eq.get(array[i])) {
                  lds[i] = lds[j]+1;
                  prev[i] = j;
              }
          }
          if(lds[i] &gt; maxlds) {
              ending = i;
              maxlds = lds[i];
          }
      }
      System.out.println(maxlds);
      for(int i = ending; i &gt;= 0; --i) {
          if(prev[i] != -1) {
              System.out.println(eq.get(array[prev[i]])); 
          }
  
      }
  </code></pre>
  
  <p>I have based this algorithm on this <a href="https://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming">SO question</a>. This code is trying to find longest decreasing subsequence instead of increasing. array[] is sorted in descending order, and I also have a hashtable with the elephants IQ's as keys for their weights.</p>
  
  <p>I'm having a hard time properly understanding DP, and I need some help.</p>
  
  <p>My algorithm seems to work fine besides tracking the chosen sequence in prev[], where it always misses one element. Does anyone know how to do this?</p>