Cho một mảng các số nguyên dương, nhiệm vụ là xóa một mảng con chứa tất cả các phần tử duy nhất. Những gì bạn nhận được khi xóa mảng con bằng tổng các phần tử của nó.
Trả về tổng tối đa của mảng con hiện tại bằng cách xóa các số hạng trước hoặc sau nó, chúng ta có thể nhận được tổng tối đa bằng cách xóa chính xác một mảng con.
Một mảng arr được gọi là một mảng con của a nếu nó tạo thành một dãy con liền kề của a nghĩa là nếu nó bằng a [l], a [l + 1], ..., a [r] cho một số (l, r). Ví dụ,
Đầu vào-1 -
arr[ ] = { 1,2,4,5,6 } Đầu ra -
17
Giải thích - Mảng con tối ưu là {2,4,5,6}.
Đầu vào-2 -
arr[ ]= {5,3,1,3,5,3,1,3,5} Đầu ra -
9
Giải thích - Mảng con tối ưu là {5,3,1} hoặc {1,3,5}.
Phương pháp tiếp cận để giải quyết vấn đề này
Để giải quyết vấn đề này, chúng ta sẽ sử dụng khái niệm Cửa sổ trượt. Kỹ thuật này cho thấy cách một vòng lặp lồng nhau có thể được chuyển đổi thành một vòng lặp đơn lẻ để giảm độ phức tạp về thời gian.
Trong kỹ thuật này, trước tiên chúng ta sẽ khởi tạo hai con trỏ cho (trái và phải) và kích thước của cửa sổ là 'win'. Trong khi lặp qua mảng, chúng tôi sẽ kiểm tra xem kích thước của một chiến thắng cụ thể có tối đa hay không. Nếu chúng tôi thấy nó tối đa, chúng tôi sẽ trả lại nó dưới dạng đầu ra.
Cách tiếp cận để giải quyết vấn đề này,
-
Lấy đầu vào là một mảng các số nguyên dương.
-
Một hàm số nguyên MaximumUniqueSubarray (vector &arr) nhận một mảng làm đầu vào.
-
Lấy ba con trỏ ‘I’, ‘j’ và kích thước cửa sổ ‘win’ và lặp qua mảng và tìm xem cửa sổ hiện tại có một phần tử nào đó có trong HashSet hay không, sau đó di chuyển cửa sổ và kiểm tra lại một phần tử khác. Nếu nó không có mặt, hãy chèn nó vào HashSet và giảm kích thước cửa sổ để xóa phần tử trước đó.
-
Tìm giá trị lớn nhất trong kết quả và giá trị cửa sổ.
-
Trả lại kết quả.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int maximumUniqueSubarray(vector<int>& arr) {
int result = 0;
unordered_set<int> hashset;
for (int i = 0, j = 0, win = 0; j < arr.size(); j++) {
while (hashset.find(arr[j]) != hashset.end()) {
hashset.erase(arr[i]);
win -= arr[i];
i++;
}
hashset.insert(arr[j]);
win += arr[j];
result = max(result, win);
}
return result;
}
int main(){
vector<int>nums;
nums<<5,3,1,3,5,3,1,3,5;
cout<<maximumUniqueSubarray(nums)<<endl;
return 0;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
9