### Minimum Maximum Partition

**Problem Setter:** Istasis Mishra

**Problem Tester:** Soham Mukherjee

**Editorialist:** Taranpreet Singh

##Problem:

Given an array of size N and an integer K. Find out the minimum and maximum cost of dividing given array into K parititons, where partitions cost of partition [l,r] is defined as A[l]+A[r].

##Solution:

This problem does not want to go for typical dp solutions that run in our mind hearing the word partitioning into K parts.

Since it is necessary to include all the elements in one partition or another, There will be a partition starting at 0 and one partition ending at N-1 position. Let’s call A[0] + A[N-1] as base cost.

Now, since we need to have all elements in one partition or another, if A* is included in ans as end of some partition other than the last one, A[i+1] will be included in ans as start of next partition.

Thus, the ideal policy if to select “Ideal Split points”, for both min cost and max cost.

**For Minimum Cost**

To determine an idea split point, maintain a min heap (PriorityQueue) and push into heap A*+A[i+1] for every i from 0 to N-2. This way, each element in heap now contains cost of increasing partition count by 1. Add first (K-1) values in min heap to base cost for Minimum cost.

**For Maximum Cost**

The logic remains same, we just use Max-heap in place of min-heap, to attain maximum cost.