php网站开发源代码,黑龙江网络公司网站建设,厦门seo外包,seo搜索引擎官网题目描述 给你一个整型数组 nums #xff0c;在数组中找出由三个数组成的最大乘积#xff0c;并输出这个乘积。 示例
示例 1
输入#xff1a;nums [1,2,3]
输出#xff1a;6示例 2
输入#xff1a;nums [1,2,3,4]
输出#xff1a;24示例 3
输入#xff1a;nums […题目描述 给你一个整型数组 nums 在数组中找出由三个数组成的最大乘积并输出这个乘积。 示例
示例 1
输入nums [1,2,3]
输出6示例 2
输入nums [1,2,3,4]
输出24示例 3
输入nums [-1,-2,-3]
输出-6题解
这个问题可以通过排序和考虑正数与负数的组合来解决。
排序首先对数组进行排序。考虑情况 ○ 如果数组中包含负数最大的乘积可能来自两个最小的负数它们的乘积为正数和一个最大的正数。 ○ 如果数组中不包含负数最大的乘积就是最大的三个数的乘积。计算最大乘积根据排序后的数组计算上述两种情况的乘积并返回较大的那个。
代码实现
int maximumProduct(vectorint nums) {sort(nums.begin(), nums.end());int n nums.size();// 情况1: 两个最小的负数和一个最大的正数int product1 nums[0] * nums[1] * nums[n - 1];// 情况2: 三个最大的正数int product2 nums[n - 1] * nums[n - 2] * nums[n - 3];return max(product1, product2);
}复杂度分析
● 时间复杂度O(n log n)其中 n 是数组 nums 的长度。主要时间消耗在排序上。 ● 空间复杂度O(1)除了输入数组外我们只使用了常数个额外变量。 这个算法通过排序和考虑两种可能的情况来计算最大乘积。
