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