GODOF_Shinobi's blog

How to solve this DP problem?
By GODOF_Shinobi, history, 6 years ago, In English

This question was asked in a hiring round. As the round is over I am asking the question. Given N elements and a positive integer K divide the array into K segments/sub arrays such that maximum of sum of segments — minimum of sum of segments is minimized. Example given N=6 and K=3 a[]={7,2,3,1,2,3} .First segment is 7 ,Second is 2,3 and the Third is 1,2,3 .Max of {7,5,6} — Min of {7,5,6} = 2. While the N is pretty small. I would be thankful to any and all solutions possible.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by GODOF_Shinobi (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The value of sum of segments is at most n^2 kinds at most. Brute-force attack the maximum and minimum values, f (idx, k, mi, ma): = Can you divide the interval of [idx, N-1] into k so that the divided minimum is mi and the maximum is ma?(bool) You can use dp.

→ Reply
»
6 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

nvm, wrong =(

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

KN^2 dp[cur][from][used] //current position considering, start of where you re considering, how many segment youve made

the transition is either go to dp[cur+1][cur+1][used+1] or go to dp[cur+1][from][used]

I'm not sure how small N or K is, so I will offer this slow dp approach.

→ Reply