title: Split up an int array into 3 parts, maximize the size of the 2 smaller parts
body: <p>Given an <code>int</code> array of length <code>n</code>, split up the array into 3 parts and make sure that the 2 smaller parts are as large as possible.</p>
  
  <p>Splitting rules: </p>
  
  <ul>
  <li>pick two indices <code>a</code> and <code>b</code> of the given array (0 &lt;= a &lt;= b &lt;= n-1)</li>
  <li>Size of first part is: sum of all array entries from index 0 to a-1 (inclusive)</li>
  <li>Size of second part is: sum of all array entries from index a to b (inclusive)</li>
  <li>Size of third part is: sum of all array entries from b+1 to n-1 (inclusive)</li>
  <li>empty parts are possible..</li>
  </ul>
  
  <p>The expected output is the sum of the 2 smaller parts (their sizes).</p>
  
  <p>Example, an array of<code>n = 6</code> and some values are given.
  The solution calculates <code>a = 2</code>, <code>b = 3</code> which splits the array into 3 parts: left part is of size <code>6 + 7 = 13</code>, middle part is <code>8 + 9 = 17</code>, right part is <code>4 + 5 = 9</code>. Output is <code>13 + 9 = 22</code> (sum of the 2 smaller parts).</p>
  
  <p>Graphical representation:</p>
  
  <p><a href="https://i.stack.imgur.com/3bn1J.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3bn1J.png" alt="Graphical representation of a wanted array split"></a></p>
  
  <p>More examples:</p>
  
  <p>[6, 8,  3, 5, 7,  2, 4, 6] should be split up into: </p>
  
  <ol>
  <li>Left (<code>6 + 8 = 14</code>)</li>
  <li>Middle (<code>3 + 5 + 7 = 15</code>)</li>
  <li>Right (<code>2 + 4 + 6 = 12</code>)</li>
  </ol>
  
  <p>Output is <code>14 + 12 = 26</code> (sum of the 2 smaller parts)</p>
  
  <p>[9, 12, 4,  7, 10, 2, 5, 8, 11, 3] should be split up into:</p>
  
  <ol>
  <li>Left (<code>9 +  12 + 4 = 25</code>)</li>
  <li>Middle (<code>7 + 10 + 2 + 5 = 24</code>)</li>
  <li>Right (<code>8 + 11 + 3 = 22</code>)</li>
  </ol>
  
  <p>Output is <code>22 + 24 = 46</code> (sum of the 2 smaller parts)</p>
  
  <p>My approach doesn't work for the given test cases:</p>
  
  <pre><code>// L is size of left part, M is size of middle part, R is size of right part
  /* I start with all array entries in the middle part, then I put elements 
     out of the middle part into the left and right part (depending on which 
     is smaller) until one of them is larger than M, this approach works for 
     many cases, two exceptions are the first 2 arrays given as examples in 
     this post. 
  */
         long a = 1;
         long b = n;
         long L = R = 0;
         long M = arr.sumOfAllArrayEntries;
         long temp;
         long[] arr = {9, 12, 4,  7, 10, 2, 5, 8, 11, 3}; 
  
         while (M &gt; Math.max(L, R)) {
              if (L &lt; R) {
                  // move leftmost element of M to L
                  temp = arr[(int) a++];
  
                  M -= temp;
                  L += temp;
  
              }
              else {
                  // move rightmost element of M to R
                  temp = arr[(int) b--];
  
                  M -= temp;
                  R += temp;
              }
          }
  
          // finds maximum of M, L, R 
          temp = Math.max(M, Math.max(L, R));
  
          // finds 2 smallest numbers out of M, L, R 
          if (temp == M)
              temp = L + R;
          else if (temp == L)
              temp = M + R;
          else if (temp == R)
              temp = M + L;
  
          // temp is equal to the sum of the 2 smaller parts
          System.out.println("Output: " + temp);
  </code></pre>