Looking at the constraints ( n <= 5000, s <= 10^7 ), how can one solve this problem. The knapsack solution is of O( n * sum ) so that will be 5 * 10^10 which is out of limits. So how can this be solved?
Does a linear time solution exist to this problem?
@bitbeast the constraints are not correct for this problem!
Test cases for this problem can be passed using knapsack approach!
Just dynamically allocate the cache.
There is some problem with the second test case. Its throwing a runtime error.
Also can we just maintain some proper data. All they have done is copied questions from other judges and that too with errors.
Yes the constraints shown are incorrect because a dp solution passes.
Test cases are fine!
also the problem constraints have been updated, check it.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.