สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n เราเลือกชุดย่อยของตัวเลขที่ระบุและลบล้างตัวเลขเหล่านี้ เราต้องหาจำนวนค่าต่างๆ สูงสุดในอาร์เรย์ที่เราหาได้
ดังนั้นหากอินพุตเป็น A =[1, 1, 2, 2] ผลลัพธ์จะเป็น 4 เพราะเราสามารถลบล้างตัวเลขตัวแรกและตัวสุดท้ายเพื่อสร้างอาร์เรย์ [-1, 1, 2, -2] ด้วย สี่ค่าที่แตกต่างกัน
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
Define one set se n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: x := A[i] if x is present in se, then: insert -x into se Otherwise insert x into se return size of se
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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
