I think you can use minimal coset representatives for this.

Each $w \in W(\Delta)$ can be uniquely written as $w_K w^K$ where $w_K \in W(\Delta_K)$ and $l(w_K) + l(w^K) = l(w)$. The element $w^K$ is called minimal left coset representative (and all of this works also for the opposite side) and the set of these is usually denoted by $W^K$. Now the Bruhat order descend to $W^K$ and you basically want the minimal (or maximal, depending on convention) element of it. I am not sure whether there is a general formula and I'd wager that chances are there is. Nevertheless, there's an algorithm that computes these minimal coset representatives in reasonable time. I've produced a patch for sage few weeks ago.

The algorithm:

1. Write $1$ over the nodes of your Dynkin diagram that doesn't belong to $K$ and write $0$ elsewhere.
2. Apply root reflections with respect to roots over which there is a positive number and treat those numbers as coefficients in the basis of fundamental weights.
3. Terminate when you arrive at a Dynkin diagram decorated only with nonpositive numbers.

The minimal representative of the longest element is then the product of simple reflections from the starting diagram to the last one. (You may need to reverse the order.)

I think you can use minimal coset representatives for this.

Each $w \in W(\Delta)$ can be uniquely written as $w_K w^K$ where $w_K \in W(\Delta_K)$ and $l(w_K) + l(w^K) = l(w)$. The element $w^K$ is called minimal left coset representative (and all of this works also for the opposite side) and the set of these is usually denoted by $W^K$. Now the Bruhat order descend to $W^K$ and you basically want the minimal (or maximal, depending on convention) element of it. I am not sure whether there is a general formula and I'd wager that chances are there is. Nevertheless, there's an algorithm that computes these minimal coset representatives in reasonable time. I've produced a patch for sage few weeks ago.

The algorithm:

1. Write $1$ over the nodes of your Dynkin diagram that doesn't belong to $K$ and write $0$ elsewhere.
2. Apply root reflections with respect to roots over which there is a positive number and treat those numbers as coefficients in the basis of fundamental weights.
3. Terminate when you arrive at a Dynkin diagram decorated only with nonpositive numbers.

The minimal representative of the longest element is then the product of simple reflections from the starting diagram to the last one. (You may need to reverse the order.)

Edit: I've just remembered that Sage contains code for computing minimal representatives (and of course also reduced expressions). The documentation is here.

So you just need to write something like

W.long_element().coset_representative(K).reduced_word()

:)