title: Maximum K sub-arrays sum
body: <p>I'm having trouble dealing with memoization and the bottom up approach algorithm for this problem: </p>
  
  <p>suppose you have an array of elements <code>xi</code> such that <code>-10000 &lt; xi &lt; 10000</code> ,for all <code>0 &lt; i &lt; N</code>. Try to find maximum sum of T elements,T &lt; N such that they are arranged in different sub-arrays.We don't sum the first element in each sub-array ,and we have to return the numbers K of sub-arrays as well.</p>
  
  <p>An example should explain :</p>
  
  <p><code>T=4,
  array = 3  9  1  1  7  =&gt; (3  9) and (1  7) have maximum sum 16= 9 + 7 ,K = 2</code></p>
  
  <p><code>T=4,
  array = 3  9  6  3  7  =&gt; (3 9 6 3) have maximum sum 18 = 9 + 6 + 3 , K = 1</code></p>
  
  <p>*T = 9, array = 14 11 18 1 1 16 12 18 0 0 11 18 9 5 14 => the contiguous sub-arrays are (14 11 18) (1 16 12 18) (11 18) K=3 and max_sum=11 + 18 + 16 + 12 + 18 + 18 = 93 ** **for T=15 array = 6 19 -29 15 9 -4 5 27 3 12 -10 5 -2 27 10 -2 11 23 -4 5 => the contiguous sub-arrays are (6 19) (-29 15 9) (5 27 3 12) (-2 27 10) (-2 11 23) with K =5 and max_sum= 19 + 15 + 9 + 27 + 3 + 12 +27 + 10 + 11 + 23=156</p>
  
  <p>This is what I've done so far : </p>
  
  <p><code>let f[i][j][0] denotes the maximal sum for the first i   slots and using j  slots, and the i-th   slot is not used.</code> </p>
  
  <p><code>let f[i][j][1] denotes the maximal gain for the first i   slots and using j slots  , and the i-th   slot is used.</code></p>
  
  <p>obviously, <code>f[i][j][k]</code> can determine <code>f[i+1][j][k]</code> or <code>f[i+1][j+1][k]</code> </p>
  
  <p>details:</p>
  
  <pre><code>    f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0],f[i][j][1]+G[i+1]);
      f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0],f[i][j][1]);
  </code></pre>