title: Can I partition the array in K sizes?
body: <p>I am trying to implement the algorithm from this question: <a href="https://stackoverflow.com/questions/8592143/need-idea-for-solving-this-algorithm-puzzle">Need idea for solving this algorithm puzzle</a>, but i am missing some edge case which is causing my code to go in infinite loop. I can fix it by doing some cosmetic change but it shows that i didn't understand the algorithm.</p>
  
  <p>Can someone help me out, what i am missing?</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  #define max(a, b) (((a)&gt;(b))?(a):(b));
  int get_max(int *a, int i, int size)
  {
      if (i &gt;= size)
          return 0;
      return max(a[i], get_max(a, i+1, size));
  }
  
  int get_sum(int *a, int i, int size)
  {
      if (i &gt;= size)
          return 0;
      return a[i] + get_sum(a, i+1, size);
  }
  
  int get_partition(int *a, int size, int bound) {
      int running_sum = 0;
      int partitions = 0, i;
  
      for (i=0;i&lt;size;i++) {
          if (a[i] + running_sum &lt;= bound) {
              running_sum += a[i];
          } else {
              running_sum = 0;
              running_sum += a[i];
              partitions++;
          }
      }
      return partitions;
  }
  
  int foo(int *a, int size, int k)
  {
      int lower = get_max(a, 0, size);
      int higher = get_sum(a, 0, size);
      int partition;
  
      while (lower &lt; higher) {
          int bound = (lower + (higher))/2;
  
          partition = get_partition(a, size, bound);
          printf("partition %d bound %d lower %d higher %d\n", partition, bound, lower, higher);
          if (partition &gt;= k) 
              lower = bound;
          else
              higher = bound;
      }
      return partition;
  }
  
  #define SIZE(a) sizeof(a)/sizeof(a[0])
  int main(void) {
      int a[] = {2, 3, 4, 5, 6};
      printf("%d\n", foo(a, SIZE(a), 3));
      return 0;
  }
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>partition 1 bound 13 lower 6 higher 20
  partition 2 bound 9 lower 6 higher 13
  partition 3 bound 7 lower 6 higher 9
  partition 3 bound 8 lower 7 higher 9
  partition 3 bound 8 lower 8 higher 9
  ...last line keeps repeating.
  </code></pre>