資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式中允許負數的陣列中成對乘積的最大和
在這個問題中，我們得到一個包含 n 個整數值（允許負值）的陣列 arr[]。我們的任務是建立一個程式來查詢允許負數的陣列中成對乘積的最大和。
問題描述 - 我們需要使用陣列的元素建立對，使得這些對的元素乘積之和最大。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {−5, 2, 3, 7, −1, 1, −3, 12}輸出
104
解釋
The pairs to be considered: (−5, −3), (2, 3), (−1, 1), (7, 12) Sum of product = (−5 * −3) + (2 * 3) + (−1 * 1) + (7 * 12) = 15 + 6 − 1 + 84 = 104.
解決方案方法
為了解決這個問題，我們將以一種使它們的乘積之和最大化的方式找到對。為了使和最大化，我們需要將相同的值配對在一起。為了使配對更容易，我們需要對陣列進行排序，然後將負數和正數配對。然後找到對中是否存在一個正數或負數或兩者都存在。如果剩餘一個正數/負數，則將其新增到對中，如果存在一個負數和一個正數，則新增它們的乘積。
演算法
初始化 -
maxSum = 0.
步驟 1 -
Sort the array arr[].
步驟 2 -
Loop for all negative values of the array. Make pairs, and add their product to maxSum.
步驟 3 -
Loop for all positive values of the array. Make pairs, and add their product to maxSum.
步驟 4 -
At last check the remaining values.
步驟 4.1 -
If one positive value remains, add it to maxSum.
步驟 4.1 -
If one negative value remains, add it to maxSum.
步驟 4.1 -
If one positive value and one negative value remains, add their product to maxSum.
步驟 5 -
Return maxSum.
示例
程式說明了我們解決方案的工作原理，
#include <bits/stdc++.h>
using namespace std;
long calcSumPairProd(int arr[], int n) {
long maxSum = 0;
sort(arr, arr + n);
int i = 0, j = (n − 1);
while (i < n && arr[i] < 0) {
if (i != n − 1 && arr[i + 1] <= 0) {
maxSum = (maxSum + (arr[i] * arr[i + 1]) );
i += 2;
}
else
break;
}
while (j >= 0 && arr[j] > 0) {
if (j != 0 && arr[j − 1] > 0) {
maxSum = (maxSum + (arr[j] * arr[j − 1]) );
j −= 2;
}
else
break;
}
if (j > i)
maxSum = (maxSum + (arr[i] * arr[j]) );
else if (i == j)
maxSum = (maxSum + arr[i]);
return maxSum;
}
int main() {
int arr[] = { −5, 2, 3, 7, −1, 1, −3, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of pairwise product in an array is "<<calcSumPairProd(arr, n);
return 0;
}輸出
The maximum sum of pairwise product in an array is 104
更新於: 2020-12-09
355 次檢視
廣告