educative.io

Educative

What if there are negative numbers

What if there are negative numbers? Can it still be solved in a dp way? Thanks!


Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5695872079757312

Hello @Harold,
Yes, the algorithm can be made work by adjusting the range of the array. In the standard DP solution, the array ranges from 0…sum and 0…n. The array size depends upon the length of the input and on one of the input parameters: the desired sum.
If all the set members are positive, and the subset-sum goes above the desired value, then the subset-sum can’t get lower later. So we only need an array that counts 0…sum.
But if we allow negative numbers, how big does our array have to be?
Suppose we arranged the numbers in a worst-case order
-90 -57 -52 -51
Then our array must have a big enough negative bound to handle the sum of all the negative numbers and a large enough positive bound to handle all the positive numbers.

I hope it is helpful.
Thank you.

1 Like