ผลรวมสูงสุดของผลคูณคู่ในอาร์เรย์ที่อนุญาตให้มีค่าลบในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่มีค่าจำนวนเต็ม n ค่า (อนุญาตให้มีค่าลบ) ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมสูงสุดของผลคูณคู่ในอาร์เรย์ที่อนุญาตให้มีค่าลบ

คำอธิบายปัญหา

เราต้องสร้างคู่โดยใช้องค์ประกอบของอาร์เรย์ โดยที่ผลรวมของผลคูณขององค์ประกอบของคู่เป็นสูงสุด

ตัวอย่าง

อินพุต

arr[] = {-5, 2, 3, 7, -1, 1, -3, 12}

เอาต์พุต

104

คำอธิบาย

คู่ที่พิจารณา: (-5, -3), (2, 3), (-1, 1), (7, 12) 
ผลรวมของผลคูณ = (-5 * -3) + (2 * 3) + (-1 * 1) + (7 * 12) = 15 + 6 - 1 + 84 = 104

แนวทางแก้ปัญหา

ในการแก้ปัญหา เราจะหาคู่ในลักษณะที่ผลรวมของผลคูณของพวกเขาเป็นสูงสุด เพื่อเพิ่มผลรวมสูงสุด เราต้องจับคู่ค่าที่มีเครื่องหมายเดียวกันเข้าด้วยกัน และเพื่อให้การจับคู่นี้ง่ายขึ้น เราต้องเรียงอาร์เรย์แล้วจับคู่ลบกับลบ และบวกกับบวก จากนั้นตรวจสอบว่ามีค่าบวกหรือลบเหลืออยู่หรือไม่ หากเหลือค่าบวกหรือลบเพียงค่าเดียว ให้เพิ่มเข้าไปในผลรวม หากเหลือค่าลบหนึ่งและค่าบวกหนึ่ง ให้เพิ่มผลคูณของพวกเขา

อัลกอริทึม

เริ่มต้น

maxSum = 0

ขั้นตอนที่ 1

เรียงอาร์เรย์ arr[]

ขั้นตอนที่ 2

วนลูปสำหรับค่าลบทั้งหมดของอาร์เรย์ สร้างคู่ และเพิ่มผลคูณของพวกเขาเข้า maxSum

ขั้นตอนที่ 3

วนลูปสำหรับค่าบวกทั้งหมดของอาร์เรย์ สร้างคู่ และเพิ่มผลคูณของพวกเขาเข้า maxSum

ขั้นตอนที่ 4

ตรวจสอบค่าที่เหลืออยู่

ขั้นตอนที่ 4.1

ถ้าเหลือค่าบวกหนึ่งค่า ให้เพิ่มเข้า maxSum

ขั้นตอนที่ 4.2

ถ้าเหลือค่าลบหนึ่งค่า ให้เพิ่มเข้า maxSum

ขั้นตอนที่ 4.3

ถ้าเหลือค่าบวกหนึ่งและค่าลบหนึ่ง ให้เพิ่มผลคูณของพวกเขาเข้า maxSum

ขั้นตอนที่ 5

คืนค่า 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