A challenge that arises in databases is how to summarize data in easy-to-display formats, such as a histogram. A problem in this context is the minimal imbalance problem. Suppose we have an array A containing n numbers, all positive, and another input k. Consider k indices j1, j2,. . . Jk that partition the array into k 1 subarrays A[1, j1], A[j1 1, j2],. . . , A[jk 1, n]. The weight w(i) of the ith subarray is the sum of its entries. The imbalance of the partition is
