title: Given a sequence of n positive integers, find a subsequence of length k such that the sum over the absolute values of the differences is maximal
body: <p>We are given a sequence of <em>n</em> positive integers, which I will denote as <em>a<sub>0</sub></em>, <em>a<sub>1</sub></em>, …, <em>a<sub>n-1</sub></em>. We are also given an integer <em>k</em>, and our task is to:</p>
  
  <ol>
  <li><p>find a subsequence of length exactly <em>k</em> (denoted as <em>b<sub>0</sub></em>, <em>b<sub>1</sub></em>, …, <em>b<sub>k-1</sub></em>), such that abs(<em>b<sub>1</sub></em> - <em>b<sub>0</sub></em>) + abs(<em>b<sub>2</sub></em> - <em>b<sub>1</sub></em>) + … + abs(<em>b<sub>k-1</sub></em> - <em>b<sub>k-2</sub></em>) is maximal; and </p></li>
  <li><p>output the sum (no need to output the entire subsequence).</p></li>
  </ol>
  
  <p>I have been trying to solve this using a dynamic programming approach but all my efforts have been futile.</p>
  
  <p><em>EDIT:</em> <em>k &lt;= n</em>. The elements in the sequence <em>b</em> must appear in the same order as they appear in <em>a</em> (otherwise, this would be solved by simply finding max, min, ... or min, max, ...).</p>
  
  <p><strong>Example input:</strong></p>
  
  <pre><code>n = 10
  k = 3
  1 9 2 3 6 1 3 2 1 3
  </code></pre>
  
  <p><strong>Output:</strong></p>
  
  <pre><code>16 (the subsequence is 1 9 1, and abs(9 - 1) + abs(1 - 9) = 8 + 8 = 16)
  </code></pre>
  
  <p>Any help / hints would be greatly appreciated.</p>