ได้รับอาร์เรย์ของจำนวนเต็มบวก งานคือลบ subarray ที่มีองค์ประกอบทั้งหมดเป็นค่าเฉพาะตัว (unique) สิ่งที่คุณได้จากการลบ subarray เท่ากับผลรวมขององค์ประกอบของมัน
คืนค่าผลรวมสูงสุดของ subarray ปัจจุบันโดยการลบพจน์ก่อนหรือหลังมัน เราสามารถได้ผลรวมสูงสุดโดยการลบ subarray เพียงหนึ่ง subarray เท่านั้น
อาร์เรย์ arr เรียกว่า subarray ของ a หากมันเป็น subsequence ที่ติดต่อกันของ a นั่นคือเท่ากับ a[l], a[l+1],..., a[r] สำหรับบาง (l,r) ตัวอย่างเช่น
ตัวอย่างอินพุต 1
arr[] = {1, 2, 4, 5, 6}
เอาต์พุต
17
คำอธิบาย
Subarray ที่เหมาะสมที่สุดคือ {2, 4, 5, 6}
ตัวอย่างอินพุต 2
arr[] = {5, 3, 1, 3, 5, 3, 1, 3, 5}
เอาต์พุต
9
คำอธิบาย
Subarray ที่เหมาะสมที่สุดคือ {5, 3, 1} หรือ {1, 3, 5}
วิธีการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะใช้แนวคิดของ Sliding Window เทคนิคนี้แสดงให้เห็นว่าลูปซ้อนสามารถแปลงเป็นลูปเดียวเพื่อลดความซับซ้อนด้านเวลาได้
ในเทคนิคนี้ เราจะเริ่มต้นตัวชี้สองตัวสำหรับ (left และ right) และขนาดของหน้าต่างเป็น 'win' ขณะวนลูปผ่านอาร์เรย์ เราจะตรวจสอบว่าขนาดของ win เฉพาะนั้นเป็นค่าสูงสุดหรือไม่ หากเราพบว่ามันสูงสุด เราจะคืนค่ามันเป็นเอาต์พุต
- รับอินพุตอาร์เรย์ของจำนวนเต็มบวก
- ฟังก์ชัน integer maximumUniqueSubarray(vector& arr) รับอาร์เรย์เป็นอินพุต
- ใช้ตัวชี้สามตัว 'i', 'j' และขนาดหน้าต่าง 'win' และวนลูปผ่านอาร์เรย์และหาว่าถ้าหน้าต่างปัจจุบันที่มีองค์ประกอบอยู่ใน HashSet แล้ว ให้เลื่อนหน้าต่างและตรวจสอบอีกองค์ประกอบ ถ้าไม่ได้อยู่ ให้แทรกลงใน HashSet และลดขนาดหน้าต่างซึ่งลบองค์ประกอบก่อนหน้า
- หาค่าสูงสุดในผลลัพธ์และค่าหน้าต่าง
- คืนค่าผลลัพธ์
ตัวอย่างโค้ด
#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 = {5, 3, 1, 3, 5, 3, 1, 3, 5};
cout << maximumUniqueSubarray(nums) << endl;
return 0;
}
ผลลัพธ์
การรันโค้ดด้านบนจะสร้างเอาต์พุตเป็น
9
