18770 差值最大

### 思路

为了找到两个数`x`和`y`使得`x - y`的值最大，并且`x`在`y`的右侧，我们可以使用以下方法：
1. 从右向左遍历数组，记录当前遍历到的最大值`max_right`。
2. 对于每个元素`a[i]`，计算`max_right - a[i]`，并更新最大差值`max_diff`。
3. 更新`max_right`为当前元素和`max_right`中的较大值。

### 伪代码

```
function find_max_diff(arr, n):
    if n == 0:
        return 0

    max_right = arr[n-1]
    max_diff = -inf

    for i from n-2 to 0:
        max_diff = max(max_diff, max_right - arr[i])
        max_right = max(max_right, arr[i])

    return max_diff
```

### C++代码

#include <iostream>
#include <vector>
#include <algorithm>int find_max_diff(const std::vector<int>& arr, int n) {if (n == 0) {return 0;}int max_right = arr[n - 1];int max_diff = -10001; // Since the absolute value of elements is not greater than 10000for (int i = n - 2; i >= 0; --i) {max_diff = std::max(max_diff, max_right - arr[i]);max_right = std::max(max_right, arr[i]);}return max_diff;
}int main() {int n;std::cin >> n;std::vector<int> arr(n);for (int i = 0; i < n; ++i) {std::cin >> arr[i];}std::cout << find_max_diff(arr, n) << std::endl;return 0;
}

### 总结

通过从右向左遍历数组并记录当前的最大值，我们可以在O(n)的时间复杂度内找到两个数`x`和`y`使得`x - y`的值最大，并且`x`在`y`的右侧。这种方法高效且适用于较大的输入规模。