How to solve this problem?

Revision en1, by it_is_not_an_alt, 2021-09-19 18:02:18

Suppose we have 2 arrays of size n (say A and B) and we have to select k indices i1,i2,i3....ik, such that all are valid indices (i.e all belong to [0,n-1) ) .And let valA = $$$\sum_{j=1}^{k} A_{ij}$$$ and let valB = $$$\sum_{j=1}^{k} B_{ij}$$$. Then min(valA,valB) should be maximum. How to solve this? I tried using dp but couldnt figure out how to move from dp[i-1] to dp[i].
Is there any other way to think about it?


  Rev. Lang. By When Δ Comment
en1 English it_is_not_an_alt 2021-09-19 18:02:18 444 Initial revision (published)