Giả sử chúng ta có hai danh sách gọi là nums và multipliers. Xét một phép toán mà chúng ta có thể loại bỏ bất kỳ số nào từ nums và loại bỏ bất kỳ số nào từ multipliers sau đó nhân chúng lại. Chúng ta phải lặp lại phép toán này cho đến khi một trong hai danh sách rỗng, tìm tổng lớn nhất của các số nhân được.
Vì vậy, nếu đầu vào là nums = [-4, 4, 3] multipliers = [-2, 2], thì đầu ra sẽ là 16, vì ta có thể ghép -4 với -2 và 4 với 2 để được -4 * -2 + 4 * 2.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:
sắp xếp danh sách nums
sắp xếp danh sách multipliers
res := 0
nếu kích thước nums < kích thước multipliers, thì hoán đổi nums và multipliers
n := kích thước nums
m := kích thước multipliers
với i từ 0 đến m - 1, thực hiện
nếu multipliers[i] <= 0, thì res := res + nums[i] * multipliers[i]
ngược lại, res := res + multipliers[i] * nums[n - (m - i)]
trả về res
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
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))
Đầu vào
[-4, 4, 3], [-2, 2]
Đầu ra
16