Min Square K Partition Problem

Min Square K Partition Problem — ExecCode Hard DSA Practice

Solve the Min Square K Partition problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Split an array into exactly k non-empty contiguous blocks. The cost of a block is the square of its sum. This is the textbook setting for Knuth / divide-and-conquer DP optimization. The same partition with a penalty on k is Aliens (Lagrangian) relaxation; a piecewise-linear convex cost is slope trick; an assignment of block boundaries can also be written as min-cost flow on a path DAG. Return the minimum total cost. If k is larger than the length of arr, return -1. You are given: arr — integers, block sums may be negative k — exact number of contiguous blocks Return minimum sum of squared block sums, or -1. A single block (k = 1) costs (total sum)^2. Order inside a block cannot change.

Examples

Input {'arr': [1, 2, 3], 'k': 1}; Output 36. Input {'arr': [1, 2, 3], 'k': 3}; Output 14. Input {'arr': [1, 2, 3], 'k': 2}; Output 18

Constraints

Blocks are contiguous and cover the array k >= 1 when n >= 1 Empty array has cost 0

Practice Min Square K Partition free on ExecCode. Browse DSA problems, topic map, and placement guides.