We only need to record a position array (pos[i]) which represent the largest number index form the i position.

For instance,

input 9 8 6 3 8

pos 0 4 4 4 4

input[pos] 9 8 8 8 8

Therefore, we only need to find the first input[i] != input[pos[i]]

and swap it.

Another example

input 5 4 3 1 2

pos 0 1 2 4 4

input[pos] 5 4 3 2 2

```
int maximumSwap(int num) {
string numString = to_string(num);
int n = numString.length();
vector<int> dpPosition(n, -1);
int curMaxPos = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (numString[i] > numString[curMaxPos]) {
curMaxPos = i;
}
dpPosition[i] = curMaxPos;
}
for (int i = 0; i < n; i++) {
if(numString[dpPosition[i]] != numString[i]) {
swap(numString[i], numString[dpPosition[i]]);
break;
}
}
return stoi(numString);
}
```