Recursive implementation of integer partition without re-arrangement

Question

Problem: Integer partition without re-arrangement

Input: An arrangement S of nonnegative numbers {s₁, . . . , s_n} and an integer k.

Output: The largest job from partitioning S into k or fewer ranges, to minimize the maximum sum over all the ranges, without reordering any of the numbers. Also the indexes of the partition dividers.

'use strict'; var sum = function(p, c) { return p + c; }; var integerPartitionRec = function(n, k, S, divider_indexes) { if (divider_indexes === undefined) divider_indexes = []; if (i === 1) return [S[0], divider_indexes]; if (k === 1) return [S.slice(0, n).reduce(sum), divider_indexes]; var cost, prefix, min_cost = Number.MAX_VALUE, min_divider_indexes = []; for (var i = 1; i < n; i++) { prefix = integerPartitionRec(i, k - 1, S, divider_indexes.concat(i)); cost = Math.max(prefix[0], S.slice(i, n).reduce(sum)); if (cost < min_cost) { min_cost = cost; min_divider_indexes = prefix[1]; } } return [min_cost, min_divider_indexes]; }; // define M[n,k] to be the minimum possible cost over all partitionings of {s1 , . . . , sn } // into k ranges, where the cost of a partition is the largest sum of elements in one of its parts. // O(kn^2) time var integerPartitionDp = function(S, k) { var n = S.length; var cache = [ [0] ]; /* Dividers */ var d = [] /* Prefix Sums */ var p = [0]; for (var i = 1; i <= n; i++) { p[i] = p[i - 1] + S[i - 1]; } for (i = 1; i <= n; i++) { cache[i] = [0, p[i]]; } for (var j = 1; j <= k; j++) { cache[0][j] = 0 cache[1][j] = S[0]; } for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { cache[i][j] = Number.MAX_VALUE; var cost; for (var x = 1; x < i; x++) { cost = Math.max(cache[x][j - 1], p[i] - p[x]); if (cost < cache[i][j]) { cache[i][j] = cost; if (d[i] === undefined) d[i] = []; d[i][j] = x; } } } } var dividers = []; var curr = d[n][k]; var count = k; while (curr !== undefined) { dividers.push(curr); curr = d[curr] ? d[curr][--count]: undefined; } return [cache[n][k], dividers]; } var run = function() { var test = [1, 2, 3, 4, 5, 6, 7, 8, 9]; console.log('S', test); console.log(integerPartitionRec(test.length, 3, test)); console.log(integerPartitionDp(test, 3)); }; run();