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 10000

    for (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`的右侧。这种方法高效且适用于较大的输入规模。

原文地址：https://blog.csdn.net/huang1xiao1sheng/article/details/142834502

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！