title: Maximum Subsequence Sum
body: <p>Given an array of integers and a threshold value, determine the maximum sum of any subsequence of the array that is less than or equal to the threshold. For all but at most 15 of the elements, either <code>array[i] &gt;= 2*array[j]</code> or <code>array[j] &gt;=2*array[i]</code> where <code>j!=i</code>.</p>
  
  <p><code>threshold</code> can be up to to 10^17, the length of the array can be up to <code>60</code>, and <code>array[i]</code> can be up to <code>10^16</code>.</p>
  
  <p>Here <code>threshold</code> is too high, so we cannot solve it by normal knapsack method. I tried it dividing this array into three parts, then getting lists of possible sums by brute force by backtracking and then merging three lists to find result. But I think there could be a more optimal way of doing this.</p>