We win some of the states and lose some of the states. Each state can be considered its own independent unit so the specific breakdown of voters inside each state determines only the winner for that state. So to maximise total voters, for each state we lost, we can assume we lost it by as small a margin as possible, and for each state we won, we can assume we got 100% of voters in that state.
Also, observe that 'losing' and 'winning' are in a sense distributive over states: losing the two states A and B is accomplished with the same amount of voters as losing the hypothetical combined state A+B. e.g. if you have a state of 10 and a state of 6, we lose if we have <5 voters in the first and <3 in the second. If we have a state of 10+6=16, we lose if we have <(5+3) voters in it. Furthermore, because people are integral quantities, the combined state will always allow for more people in a loss than its constituent states (in the above example, we lose with a maximum of 7 in the combined state, but a maximum of 4+2 in the constituent states). With a more formal argument, I believe you can treat any set of state wins and losses as two states: a state we won and a state we lost. The maximum proportion of voters would occur when for these two states, B has one more person than A, and we win A with 100% of voters and lose B with 49.99..% of voters. For sufficiently large populations, 75% of the population can vote for us and we can still lose.
