UVA-11059 最大乘积 题解答案代码 算法竞赛入门经典第二版

**UVA-11059 最大乘积**

**题目描述**

给定一个长度为 n 的序列，求出该序列中两个数字的最大乘积。

**输入输出格式**

* 输入：一行 n 个整数。
* 输出：一个整数，表示两个数字的最大乘积。

**算法思路**

1. **找到最大的两个数**: 我们需要找到序列中两个数字的最大乘积。我们可以先将序列中的所有数字排序，然后从后面开始取两个数字。
2. **考虑负数**: 如果序列中有负数，我们需要特别注意，因为负数与正数相乘会得到一个较大的负数，而不是一个较大的正数。

**代码实现**

cpp#include <iostream>
using namespace std;

int main() {
 int n, a[1000], max1 = -2147483648, max2 = -2147483648;
 cin >> n;
 for (int i =0; i < n; i++) {
 cin >> a[i];
 if (a[i] > max1) {
 max2 = max1;
 max1 = a[i];
 } else if (a[i] > max2 && a[i] != max1)
 max2 = a[i];
 }
 cout << max1 * max2 << endl;
 return0;
}

**注释**

* 我们首先定义了一个变量 `max1` 和 `max2` 来存储序列中两个数字的最大乘积。
* 然后，我们使用一个循环来读取序列中的所有数字，并将它们存储在数组 `a` 中。
* 在每次迭代中，我们检查当前数字是否大于 `max1`。如果是，则我们更新 `max2` 为 `max1` 的值，然后更新 `max1` 为当前数字的值。如果当前数字不等于 `max1`且大于 `max2`，则我们更新 `max2` 为当前数字的值。
* 最后，我们输出 `max1 * max2` 作为结果。

**时间复杂度**

* 时间复杂度为 O(n)，其中 n 是序列中的数字数量，因为我们需要遍历整个序列才能找到两个数字的最大乘积。

**空间复杂度**

* 空间复杂度为 O(1)，因为我们只使用了常数个变量来存储结果，而不需要额外的空间。