题目

杨喻新渝的面试题，数组中数对<a, b>, a出现的位置在b之前，求b - a的最大值（辅助最大最小数组，类似接雨水的做法）

思路

• 对于当前位置nums[i]，其右侧区间[i, n - 1]当中，最大值为right_max[i]，其差值为right_max[i] - nums[i]
• 建立right_max[i]，从右往左扫描一次即可
• 读取每个nums[i]的差值，从左往右扫描一次即可

  代码

  ```cpp

  include

  include

  include

  include

  using namespace std;

int main() { int n = 10; int seed = time(0); srand(seed); vector nums(n, 0); for (int i = 0; i < n; i++) { nums[i] = rand() % 100 + 1; }

vector<int> right_max(nums);
for (int i = n - 2; i >= 0; i--) {
    right_max[i] = max(right_max[i + 1], nums[i]);
}
int maxsub = 0;
for (int i = 0; i < n; i++) {
    maxsub = max(right_max[i] - nums[i], maxsub);
}
for (int i = 0; i < n; i++) {
    cout << nums[i] << " ";
}
cout << endl;
for (int i = 0; i < n; i++) {
    cout << right_max[i] << " ";
}
cout << endl;
cout << maxsub << endl;
return 0;

} ```