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:
- Cost of selecting a subarray from index I to index j (i<=j) is cost[i] + cost[j]
- 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
This from the interviewbit ongoing contest I suppose.