โปรแกรม C++ นับค่าที่แตกต่างได้สูงสุดหลังกลับเครื่องหมายซับอาร์เรย์

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

สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ เลือกซับเซตใดก็ได้ของตัวเลขที่กำหนดและกลับเครื่องหมายตัวเลขเหล่านั้น ต้องการหาจำนวนค่าที่แตกต่างกันสูงสุดในอาร์เรย์ที่ได้

ตัวอย่าง: A = [1, 1, 2, 2] ผลลัพธ์คือ 4 เพราะสามารถกลับเครื่องหมายตัวแรกและตัวสุดท้ายได้อาร์เรย์ [-1, 1, 2, -2] ที่มี 4 ค่าต่างกัน

ขั้นตอนการแก้ปัญหา

กำหนดเซต se
n := ขนาดของ A
สำหรับ i := 0 ถึง n-1:
    x := A[i]
    ถ้า x อยู่ใน se แล้ว:
        ใส่ -x ลงใน se
    มิฉะนั้น:
        ใส่ x ลงใน se
คืนค่าขนาดของ se

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    set<int> se;
    int n = A.size();
    for (int i = 0; i < n; i++) {
        int x = A[i];
        if (se.count(x))
            se.insert(-x);
        else
            se.insert(x);
    }
    return se.size();
}

int main() {
    vector<int> A = { 1, 1, 2, 2 };
    cout << solve(A) << endl;
}

อินพุต

{ 1, 1, 2, 2 }

เอาต์พุต

4