โปรแกรมหาผลรวมสูงสุดของตัวเลขคูณกันใน Python

การหาผลรวมสูงสุดจากการจับคู่คูณระหว่างสองรายการ

กำหนด nums และ multipliers จับคู่คูณกัน (นำออกจากรายการ) จนรายการใดรายการหนึ่งหมด หาผลรวมสูงสุด

อัลกอริทึม

1. เรียง nums และ multipliers ทั้งคู่
2. ถ้า len(nums) < len(multipliers) สลับกัน
3. จับคู่ multipliers ตัวลบ/ศูนย์ กับ nums ตัวเล็กสุด (ซ้าย)
4. จับคู่ multipliers ตัวบวก กับ nums ตัวใหญ่สุด (ขวา)

ตัวอย่างโค้ด

def solve(nums, multipliers):
    nums.sort()
    multipliers.sort()
    res = 0
    if len(nums) < len(multipliers):
        nums, multipliers = multipliers, nums
    n, m = len(nums), len(multipliers)
    for i in range(m):
        if multipliers[i] <= 0:
            res += nums[i] * multipliers[i]
        else:
            res += multipliers[i] * nums[n - (m - i)]
    return res

nums = [-4, 4, 3]
multipliers = [-2, 2]
print(solve(nums, multipliers))

ผลลัพธ์

16

คำอธิบาย

เรียง nums: [-4, 3, 4], multipliers: [-2, 2]

• multipliers[0] = -2 (ลบ) × nums[0] = -4 → 8
• multipliers[1] = 2 (บวก) × nums[2] = 4 → 8
• ผลรวม = 16