คำอธิบาย
มีอาร์เรย์ขนาด (2 × n − 1) จำนวนเต็ม เราสามารถเปลี่ยนเครื่องหมายของ n องค์ประกอบได้พอดี กล่าวคือ เลือก n องค์ประกอบ และคูณแต่ละตัวด้วย -1 หาผลรวมสูงสุดของอาร์เรย์
ตัวอย่าง
ถ้าอินพุตอาร์เรย์คือ {-2, 100, -3} เราสามารถได้ผลรวมสูงสุดโดยเปลี่ยนเครื่องหมาย -2 และ -3 หลังเปลี่ยนอาร์เรย์กลายเป็น
{2, 100, 3} และผลรวมสูงสุดคือ 105
อัลกอริทึม
- นับจำนวนตัวเลขลบ
- คำนวณผลรวมของอาร์เรย์โดยใช้ค่าสัมบูรณ์ของตัวเลข
- หาตัวเลขขั้นต่ำของอาร์เรย์โดยใช้ค่าสัมบูรณ์
- ตรวจสอบว่าจำนวนตัวเลขลบเป็นคี่ และ n เป็นคู่ แล้วลบ 2×m จากผลรวม และนี่คือผลรวมสูงสุด มิฉะนั้น ผลรวมคือคำตอบ
- ทำซ้ำขั้นตอนข้างต้น (2 × n − 1) ครั้ง
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int* arr, int n) {
int negtiveCnt = 0;
int sum = 0;
int m = INT_MAX;
for (int i = 0; i < 2 * n - 1; ++i) {
if (arr[i] < 0) {
++negtiveCnt;
}
sum = sum + abs(arr[i]);
m = min(m, abs(arr[i]));
}
if (negtiveCnt % 2 && n % 2 == 0) {
sum = sum - 2 * m;
return sum;
}
return sum;
}
int main() {
int arr[] = {-2, 100, -3};
int n = 2;
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
}
ผลลัพธ์
Maximum sum = 105
