一个包含n（2<=n<=50）个实数的数列，从中找2个数，使得这两个数的差是最大的。

算法1：暴力枚举

最朴素的思路就是对于每个数，遍历剩下的数，算出与它的差，取最大值即可。时间复杂度为$O(n^2)$，可以通过本题。

时间复杂度

枚举每个数需要$O(n)$的时间，总共需要枚举$n$个数，因此时间复杂度为$O(n^2)$。

C++ 代码

class Solution {
public:
double maxDiff(vector<double>& nums) {
double ans = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ans = max(ans, abs(nums[i] - nums[j]));
}
}
return ans;
}
};

算法2：排序+双指针

如果能将数组排序，那么最大差值一定出现在数组中的相邻两个数之间。因此，将数组排序后，遍历一遍数组，计算相邻两个数的差值，取最大值即可。

时间复杂度

排序需要$O(n\log n)$的时间，遍历一遍数组需要$O(n)$的时间，因此时间复杂度为$O(n\log n)$。

C++ 代码

class Solution {
public:
double maxDiff(vector<double>& nums) {
double ans = 0;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 1; i < n; i++) {
ans = max(ans, nums[i] - nums[i - 1]);
}
return ans;
}
};

算法3：最大最小值

遍历一遍数组，同时记录最大值和最小值，最大差值即为最大值减去最小值。

时间复杂度

遍历一遍数组需要$O(n)$的时间，因此时间复杂度为$O(n)$。

C++ 代码

class Solution {
public:
double maxDiff(vector<double>& nums) {
double ans = 0;
int n = nums.size();
double min_num = nums[0], max_num = nums[0];
for (int i = 1; i < n; i++) {
min_num = min(min_num, nums[i]);
max_num = max(max_num, nums[i]);
ans = max(ans, max_num - min_num);
}
return ans;
}
};