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. The input consists of an array A containing n positive numbers and an integer k. Consider k indices j1.j2,.jk that partition the array into k+1 subarrays A[1j1], Alj1 +1.j2), ., A[jk + 1, n]. The weight w(i) of the ith subarray is the sum of its entries. The LA1 k +1 max w(i) imbalance of the partition is That is, the imbalance is the maximum deviation of any partition from the average size. a) Give an algorithm for determining the partition with minimal imbalance given A, n and k. (This basically corresponds to finding a histogram with k + 1 bars as close to equal as possible.) b) Explain how your algorithm would change if the imbalance was redefined to be LA k +1