We have create a dp array as we create a lookup table called dp of rows of size n
and
2∗sum(arr)+1
columns.
Why is it 2*sum(arr) +1;
Hello @VISHAL_SINGH,
Thank you for sharing this feedback. 1. Let’s see why have we chosen the size of the dp table as 2 * sum(arr) + 1.
The total variable represents the maximum possible positive sum you can obtain by adding all elements of the arr array, which is sum(arr). Similarly, the minimum possible negative sum you can obtain is -total. So, the range of possible sums you need to consider is from -total to total.
To represent this range of sums in the dp array, we need an array with a size of 2 * total + 1. This allows you to cover both positive and negative sums, with total at the center of the array.
Note: You can understand this by looking at the illustration slides just above the code widget.
In summary, the size of the dp table is 2 * total + 1 to cover the range of possible sums that can be achieved using the elements of the arr array, including both positive and negative sums.
Hope this answers your query, please feel free to share any more suggestions and feedbacks.
Happy learning.
Hi @VISHAL_SINGH,
I’d like to mention a small edit.
To represent this range of sums in the dp array, i.e., -total to total, we need an array with a size of 2 * total + 1. This allows you to cover all sums from -total to +total, including 0.
Hope this helps in understanding why we are creating the lookup table in this way.
Happy learning!