Trace distance expressed with maximization of probabilities I'm studying chapter 9 of Nielsen and Chuang, where trace distance is defined by equation (9.1) $D(p_x,q_x)=\dfrac{1}{2}\sum_{x}|p_x-q_x|$ and later on the next page (also asked to be proven in exercise 9.4) $D(p_x,q_x)=\underset{\Large{s}}{\max}|p(S)-q(S)|=\underset{\Large{s}}{\max}|\underset{x\in S}{\sum}p_x-\underset{x\in S}{\sum}q_x|$ equation (9.3). 
I thought this $\underset{\Large{s}}{\max}$ means that, over the space $S$ I choose two values for $p_x$ and $ q_x$ that creates the maximal distance. However by doing so I feel like I'm making an approximation. How come this is not an approximation. 
How should I proceed with this proof;
$$D(p_x,q_x)=\dfrac{1}{2}\sum_{x}|p_x-q_x|=\dfrac{1}{2}(\underset{p_x>q_x}\sum(p_x-q_x)-\underset{q_x>p_x}\sum(p_x-q_x) )$$
$$\underset{q_x>p_x}\sum(p_x-q_x) =\underset{q_x>p_x}\sum p_x-\underset{q_x>p_x}\sum q_x=1-\underset{p_x>q_x}\sum p_x-(1-\underset{p_x>q_x}\sum q_x)$$
putting this to above equation
$$D(p_x,q_x)=\underset{p_x>q_x}\sum p_x-q_x$$
How come this equality will be equal to maximization? 
 A: You were essentially already there with the derivation.
You found that
$$\sum_{q_x>p_x}(p_x-q_x)=-\sum_{p_x>q_x}(p_x-q_x),$$
which used in the last equation you wrote for $D(p_x,q_x)$ gives you
$$\frac12\left[\sum_{p_x>q_x} (p_x-q_x)-\sum_{q_x>p_x}(p_x-q_x)\right]
=\sum_{p_x>q_x} (p_x-q_x).$$
This is what you were trying to prove, with $S_M\equiv\{i: p_x>q_x\}$.
To see that $S_M$ maximises the expression $d(S)\equiv|p(S)-q(S)|$, rewrite it as
$$d(S)= |p(S)-q(S)|=\left\lvert\sum_{x\in S}(p_x-q_x)\right\rvert.$$
Assume $S$ is such that $p(S)\ge q(S)$. Then $d(S)=p(S)-q(S)$, and if there is some $x\in S$ such that $p_x< q_x$, then the set $S'\equiv S\setminus \{x\}$ is such that $d(S')\ge d(S)$.
Similarly, if $p_x>q_x$ and $S'\equiv S\cup\{x\}$, then $d(S')\ge d(S)$.
In other words, the set $S_M$ maximises $d(S)$, because any other set of points can be modified by removing/adding at least one point increasing the value of $d(S)$.
If on the other hand $p(S)<q(S)$, then $d(S)=q(S)-p(S)$. By similar reasoning, we get that the set $S_m\equiv\{x: q_x\ge p_x\}=\bar S_M$ (where $\bar X$ denotes the complement of $X$) maximises $d(S)$.
Observing that $d(S_M)=d(s_m)$ allows to conclude that $S_M$ does indeed maximise $d(S)$.
You can also have a look at this other question on quantumcomputing.SE for more information about how to derive expressions for the trace distance.
