title: faster algorithms for minimum maximum contiguous k partition
body: <p>I was reading this <a href="http://www.cas.mcmaster.ca/%7Eterlaky/4-6TD3/slides/DP/DP.pdf" rel="nofollow noreferrer">http://www.cas.mcmaster.ca/~terlaky/4-6TD3/slides/DP/DP.pdf</a> and would like to know if there exists a solution with better time complexity to the partition problem.</p>
  <p>From the link:</p>
  <blockquote>
  <p>&quot;Suppose a given arrangement S of non-negative numbers
  {s1,...,sn} and an integer k. How to <strong>cut</strong> S into k or fewer ranges,
  so as to minimize the maximum sum over all the ranges?&quot;</p>
  </blockquote>
  <p>e.g.</p>
  <blockquote>
  <p>S = 1,2,3,4,5,6,7,8,9</p>
  <p>k=3</p>
  <p>By cutting S into these 3 ranges, the sum of the maximum range (8,9) is 17, which is the minimum possible.</p>
  <p>1,2,3,4,5|6,7|8,9</p>
  </blockquote>
  <p>The algorithm suggested in the link runs in O(kn^2) and uses O(kn) space. Are there more efficient algorithms?</p>