How to solve this problem?

Правка en1, от Electr0, 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. Язык Кто Когда Δ Комментарий
en1 Английский Electr0 2021-09-19 18:02:18 444 Initial revision (published)