Giả sử chúng ta có một số mảng là các số nguyên, chúng ta có thể thực hiện một số thao tác trên mảng. Ở đây trong mỗi thao tác, chúng tôi chọn bất kỳ nums [i] nào và xóa nó để kiếm được số điểm nums [i]. Chúng ta phải xóa mọi phần tử bằng nums [i] - 1 hoặc nums [i] + 1. Ban đầu điểm bằng 0. Chúng ta phải tìm số điểm tối đa mà chúng ta có thể kiếm được bằng cách áp dụng các phép toán đó. Vì vậy, nếu đầu vào là [3,4,2], thì đầu ra sẽ là 6. Vì vậy, điều này là bởi vì, nếu chúng ta xóa 4, chúng ta sẽ nhận được 4 điểm, do đó 3 cũng sẽ bị xóa. Sau đó xóa 2 để được 2 điểm. Tổng cộng 6 điểm đã kiếm được.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của mảng nums, xác định bản đồ m, ret:=0, lưu trữ tần số của các phần tử trong nums thành m
-
cnt:=0
-
cho mỗi cặp nó là m
-
x:=key của nó
-
temp:=x * giá trị của nó
-
it1:=trỏ tới phần trước của nó và it2:=trỏ đến phần trước của it1
-
if cnt> =1 and x - key of it1> 1, then temp:=m [key of it1]
-
ngược lại khi cnt> =2 thì temp:=temp + m [key of it2]
-
a =m [key of it1] nếu cnt> =1, nếu không thì 0
-
m [key of it]:=max of temp và a
-
ret:=max của ret và temp
-
tăng cnt lên 1
-
-
trả lại ret
Ví dụ (C ++)
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;
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int n = nums.size();
map <int, int> m;
int ret = 0;
for(int i = 0; i < nums.size(); i++){
m[nums[i]]++;
}
int cnt = 0;
map <int, int> :: iterator it = m.begin();
while(it != m.end()){
int x = it->first;
int temp = x * it->second;
map <int, int> :: iterator it1 = prev(it);
map <int, int> :: iterator it2 = prev(it1);
if(cnt >= 1 && x - it1->first > 1){
temp += m[it1->first];
}
else if(cnt >= 2){
temp += m[it2->first];
}
m[it->first] = max(temp, cnt >= 1 ? m[it1->first] : 0);
ret = max(ret, temp);
it++;
cnt++;
}
return ret;
}
};
main(){
vector<int> v = {3,4,2};
Solution ob;
cout << (ob.deleteAndEarn(v));
} Đầu vào
[3,4,2]
Đầu ra
6