You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Find the most likely number of wins.
For example, if n = 2 and P = [0.4, 0.2], the most likely number of wins is 0, with a probability of .6 ∗ .8 = .48 (P(1) = .4*.8+.6*.2 = .44 and P(2) = .4 * .2 = .08).
I understand how to do this manually: if I want to find P(x) wins I add up the probabilities of the outcomes that result in x wins. Is there an algorithmic way of doing this more efficiently? The problem seems to lend itself to some sort of dynamic programming solution but I'm unsure.
My first instinct was to construct an array R such that R[i] is the probability your team wins i games. The only computation this saves you though is if you have a max element greater than the remaining probability possible (if n = 5 and R(0) = .4 and R(1) = .3, you know that none of the elements R[2:5] are going to be the max). I'm not doing much to break the problem into subproblems. Based on the other dynamic programming questions I've seen, it feels like there's something more slick that I'm missing.
example with Ivan's solution