Hello Folks,

I recently came across this problem. I was able to solve it with DP with time complexity of O(N^N*K) but was wondering if there is another approach (like Binary Search) to solve it in a better TC.

Problem Statement:

Given an array of N numbers and an array of cost for selecting each index, partition the main array it into K contiguous subarrays, such that:

1. Cost of selecting a subarray from index I to index j (i<=j) is cost[i] + cost[j]
2. All the k selected subarray are contiguous and non-empty

Now, we need to find two things: 1. Maximum possible cost we can obtain 2. Minimum possible cost we can obtain

Constraints: K<=N<=1e5 cost[i] <= 1e8