Giả sử chúng ta có một mảng A với n phần tử. Chúng tôi chọn bất kỳ tập hợp con nào của các số đã cho và phủ định các số này. Chúng tôi phải tìm số lượng lớn nhất các giá trị khác nhau trong mảng mà chúng tôi có thể nhận được.
Vì vậy, nếu đầu vào là A =[1, 1, 2, 2], thì đầu ra sẽ là 4, vì chúng ta có thể phủ định các số đầu tiên và cuối cùng để tạo mảng [-1, 1, 2, -2] với bốn giá trị khác nhau.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
{ 1, 1, 2, 2 } Đầu ra
4