Company: Zorvyn SDE_3april
Difficulty: medium
Problem Statement You are given an array A of N positive integers. You need to partition this array into exactly k non-empty contiguous subarrays such that the cost of the partition is minimized. The cost of a partition is defined as the sum of the costs of each subarray, where the cost of a subarray is calculated as: cost(subarray) = (max_element - min_element) * length_of_subarray In other words, for each subarray, you multiply the range (difference between maximum and minimum elements) by the number of elements in that subarray. Task Find the minimum possible cost to partition the array into exactly k contiguous subarrays. Input Format First line contains two space-separated integers N and k . Second line contains N space-separated integers representing array A . Output Format Print a single integer - the minimum cost to partition the array into exactly k subarrays. Examples Example 1 Input: 5 2 1 3 2 5 4 Output: 8 Explanation: Optimal partition is [1, 3, 2] and [5, 4] : Cost of [1,