rahul_9812's blog

By rahul_9812, history, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it