Optimisation problem

Revision en1, by harsh-apcr, 2024-03-31 19:59:32

Given two arrays of integers $$$x$$$ and $$$y$$$, of length $$$n$$$, find a partition of indices $$${1, \ldots, n}$$$ such that you minimise the score, where the score of a partition $$$S_1, S_2$$$ is defined as $$$\max(\sum \limits_{j \in S_1} x[j], \sum \limits_{j \in S_2} y[j])$$$

just find the minimum score that can be achieved, I fancy a dp approach, any help is appreciated, thanks

Tags #dynamic-programming, #optimization, #array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English harsh-apcr 2024-03-31 21:48:47 138
en1 English harsh-apcr 2024-03-31 19:59:32 390 Initial revision (published)