问题描述在一次数学竞赛中小C和小红被要求从一个整数数组中找出三个不同的数字使得它们的乘积最大。但是有一个规则这三个数字必须来自数组中的不同位置且不能是同一个数字重复使用即使数组中有重复数字每个位置也只能用一次。小C和小红需要合作设计一个高效的算法来解决这个问题以便在竞赛中胜出。要求设计一个算法时间复杂度为 O(n log n) 或更优其中 n 是数组的长度。考虑数组可能包含正数、负数和零的情况因为乘积的最大值可能由两个负数和一个正数相乘得到例如两个负数相乘为正再乘以一个正数会更大。测试样例样例1输入nums [1, 2, 3, 4]输出24解释最大的三个数字是 2, 3, 4乘积为 2 * 3 * 4 24。样例2输入nums [-10, -10, 1, 2, 3]输出300解释最大的乘积来自两个负数和一个正数-10 * -10 * 3 300。样例3输入nums [-1, -2, -3, -4]输出-6解释所有数字都是负数乘积最大的是三个最大的负数即绝对值最小的-1 * -2 * -3 -6。约束条件3 ≤ nums.length ≤ 10^4-1000 ≤ nums[i] ≤ 1000数组中的整数可以是正数、负数或零保证至少存在三个不同的数字但可能重复程序代码#include stdio.h#include stdlib.h// 升序比较函数int cmp(const void* a, const void* b) {return (*(int*)a) - (*(int*)b);}int maximumProduct(int* nums, int numsSize) {// 升序排序qsort(nums, numsSize, sizeof(int), cmp);int n numsSize;// 情况1最大的三个数int p1 nums[n-1] * nums[n-2] * nums[n-3];// 情况2两个最小的数 × 最大的数int p2 nums[0] * nums[1] * nums[n-1];return p1 p2 ? p1 : p2;}int main() {int nums1[] {1, 2, 3, 4};int nums2[] {-10, -10, 1, 2, 3};int nums3[] {-1, -2, -3, -4};printf(%d\n, maximumProduct(nums1, 4)); // 24printf(%d\n, maximumProduct(nums2, 5)); // 300printf(%d\n, maximumProduct(nums3, 4)); // -6return 0;}#include stdio.h #include stdlib.h // 升序比较函数 int cmp(const void* a, const void* b) { return (*(int*)a) - (*(int*)b); } int maximumProduct(int* nums, int numsSize) { // 升序排序 qsort(nums, numsSize, sizeof(int), cmp); int n numsSize; // 情况1最大的三个数 int p1 nums[n-1] * nums[n-2] * nums[n-3]; // 情况2两个最小的数 × 最大的数 int p2 nums[0] * nums[1] * nums[n-1]; return p1 p2 ? p1 : p2; } int main() { int nums1[] {1, 2, 3, 4}; int nums2[] {-10, -10, 1, 2, 3}; int nums3[] {-1, -2, -3, -4}; printf(%d\n, maximumProduct(nums1, 4)); // 24 printf(%d\n, maximumProduct(nums2, 5)); // 300 printf(%d\n, maximumProduct(nums3, 4)); // -6 return 0; }运行结果