#### Algorithm

- Find the first local minima (or an inflexion point) left-to-right
- If no local minima found, return the number unmodified
- Otherwise, a swap is certain; swapping the local minima and its right neighbor will definitely give a larger number

- But can we do better?
- Find the max in the rest of the range, i.e. to the right of the local minima
- Swapping the local minima and the max will definitely give another larger number

- But can we do even better?
- Go back leftwards starting from the local minima finding the max value smaller than the max found above

- Swap away!

#### Code

```
// Time : O(n), at most 2 passes
// Space : O(1)
int maximumSwap(int num)
{
auto str = to_string(num);
// Find the first local minima (or an inflexion point) left-to-right
int n = str.size(), li = 0;
for ( ; li < n - 1 && str[li] >= str[li + 1]; ++li);
// If no local minima found, return the number unmodified
if (li == n)
return num;
// Otherwise, a swap is certain; swapping the values in indices li and (li + 1)
// will definitely give a larger number
// But can we do better?
// Find the max in the rest of the range, i.e. to the right of li
int maxi = n - 1;
for (int ri = maxi - 1; ri > li; --ri)
if (str[ri] > str[maxi])
maxi = ri;
// Swapping the values in indices li and maxi will definitely give another
// larger number
// But can we do even better?
// Go back leftwards starting from li finding the max value smaller than the
// max found above
for ( ; li > 0 && str[li - 1] < str[maxi]; --li);
swap(str[li], str[maxi]);
return stoi(str);
}
```

#### Examples

- 93458
- local minima is 3; max to the right of it is 8;
**no larger value to the left of 3 is smaller than the max, 8**
- swap 3 and 8 to get 98453

- 76489
- local minima is 4; max to the right of it is 9; max value to the left of the local minima, 4, smaller than the max value, 9, is 7
- swap 7 and 9 to get 96487

- 2649
- local minima is 2; max to the right of it is 9
- swap 2 and 9 to get 9642

- 88888829
- local minima is 2; max to the right of it is 9; max value to the left of the local minima, 2, smaller than the max value, 9, is the leftmost 8
- swap the leftmost 8 and 9 to get 988888828