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