用C语言实现:输入一个包含 n个整数的数组 a ,求数组中两个不同下标的数 a[i] 和 a[j] (i≠j ),使得 a[i]×a[j] 的值最大。其中2≤n≤10^5 ,−10^6≤a[i]≤10^6
时间: 2023-05-29 13:01:15 浏览: 95
【题目描述】
输入一个包含 n 个整数的数组 a,求数组中两个不同下标的数 a[i] 和 a[j] 使得 a[i]*a[j] 的值最大。其中 2≤n≤10^5,−10^6≤a[i]≤10^6。
【样例输入】
5
-2 3 1 -5 0
【样例输出】
10
【分析】
首先想到的是暴力解法,两重循环枚举每一对不同下标,但这样时间复杂度是 O(n^2),显然会超时。考虑优化。
因为这里要求的是两个数相乘的最大值,我们可以将数组中的数按照绝对值大小从大到小排序,然后将排在前面的正数和排在后面的负数相乘,即可找到乘积最大的两个数。
但是如果数组中只有正数或只有负数,则没法同时选出两个数,因此需分类讨论:
1. 数组中有正数和负数
将数组中的数按照绝对值大小从大到小排序,然后找到第一个正数的下标和最后一个负数的下标,对应的两个数相乘即可。
2. 数组中只有正数或只有负数
最大的两个数相乘即可。
【代码实现】
相关问题
用C语言实现:输入一个包含 n个整数的数组 a ,求数组中两个不同下标的数 a[i] 和 a[j] (i≠j ),使得 a[i]×a[j] 的值最大。
可以用两层循环遍历数组中的每一对不同的数,比较它们的乘积是否大于之前的最大乘积,如果是则更新最大乘积和对应的下标:
```c
#include <stdio.h>
int main() {
int n, a[100], max_product = -1, max_i, max_j;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
int product = a[i] * a[j];
if (product > max_product) {
max_product = product;
max_i = i;
max_j = j;
}
}
}
printf("Max product %d achieved at indices %d and %d\n", max_product, max_i, max_j);
return 0;
}
```
用C语言实现:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
好的,下面是用C语言实现的代码:
```c
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i, j;
int* res = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
for(i = 0; i < numsSize - 1; i++){
for(j = i + 1; j < numsSize; j++){
if(nums[i] + nums[j] == target){
res[0] = i;
res[1] = j;
return res;
}
}
}
return NULL;
}
```
这段代码使用了双重循环,依次遍历数组中的每一个元素,找到其中两个元素的和等于目标值,返回它们的下标。