title: Longest convex subsequence in an array
body: <p>Suppose we are given an input array of integers, how to find the longest convex subsequence that satisfies the following condition:</p>
  
  <pre><code>c[i] &lt; (c[i-1] + c[i+1]) / 2
  </code></pre>
  
  <p><code>c[i-1]</code>, <code>c[i]</code> and <code>c[i+1]</code> are three consecutive elements in the subsequence.</p>
  
  <p>For example, if input array is <code>{ 1, 2, -1, 0, 3, 8, 5 }</code>, the longest convex subsequence should be: <code>{ 1, -1, 0, 3, 8 }</code> or <code>{ 2, -1, 0, 3, 8 }</code>.</p>
  
  <p>I tried to solve this problem using the same dynamic programming idea in "Longest Increasing Subsequence" (LIS) problem. But because each element in the subsequence depends on the previous two elements, it seems that an O(n^2) solution is impossible. Thank you for your help.   </p>