Partition Array into K Sectors – Minimum and Maximum Cost Microsoft - Indian Institute of Technology, Guwahati

Problem Preview

"**Mode:** On-Campus **Exam Pattern:** 2 coding **OA Date:** 2026-08-10 ## Partition Array into K Sectors – Minimum and Maximum Cost You are given an array A of size N and an integer K. You need to partition the array into exactly K non-empty, contiguous, non-overlapping sectors. The cost of each sector is defined as: \[ \text{Cost}(L,R)=A[L]+A[R] \] where A[L] and A[R] are the first and last elements of that sector. Calculate: 1. The minimum possible total cost among all valid partitions. 2. The maximum possible total cost among all valid partitions. The total cost of a partition is the sum of the costs of all its sectors. Example: N = 5 K = 2 A = [1, 5, 3, 4, 2]"