Hi, I’m getting WA for the SUBINC problem on only one test case and I can not figure where it comes from.
Here is my code implementation !
My approach is the folowing :
(1) Increment through the array while it is in a non-decreasing order.
(2) Once you get to a number that breaks this rule or you are at the end of the array, compute the number of subsets folowing the rule you already have.
(3) Repeat steps (1) and (2) from the new index and until you get to the end of the array.
Example :
Given the array [2, 5, 7, 4] :
(1)
Is 2 >= 2 ? Yes. Keep going.
Is 5 >= 2 ? Yes. Keep going.
Is 7 >= 5 ? Yes. Keep going.
Is 4 >= 7 ? No. Stop here.
(2)
[2, 5, 7] is a non-decreasing subset. From its size only, you can get the numbers of subset in this subset that follow the rule using the combination formula. We are actually looking for the number of pairs of indexes amongst this subset. It is therefore equals to \binom {size+1}2. In this case we increase our count by \binom 42 = 6.
(3)
Keep going.
(1)
Is 4 >= 4 ? Yes. Keep going.
End of array. Stop here.
(2)
Increase the count by \binom 22 = 1.
(3)
End of array. End of program, return the count which here is equal to 6+1 = 7.
I’m looking forward to getting some help on this !
Thanks