สมมติว่าเรามีอาร์เรย์ของ N จำนวนเต็มที่มีงานคือหาความยาวของ subarray ที่มีความยาวสูงสุด หากไม่มี subarray ใดที่มีความยาวสูงสุดหรือผลรวมเท่ากับ 0 ให้คืนค่า '0' ตัวอย่างเช่น
ตัวอย่างอินพุต 1
N = 8, A[] = {15, -5, -1, 5, 1, 4}
เอาต์พุต
4
คำอธิบาย
Subarray ที่ใหญ่ที่สุดที่มีผลรวมเป็นศูนย์คือ {-5, -1, 5, 1} ซึ่งมีความยาว 4
ตัวอย่างอินพุต 2
N = 5, A[] = {3, 2, 4, 8, -1}
เอาต์พุต
0
คำอธิบาย
เนื่องจากไม่มี subarray ใดที่มีผลรวมเท่ากับศูนย์ เอาต์พุตคือ '0'
วิธีการแก้ปัญหา
มีหลายวิธีในการแก้ปัญหานี้ อัลกอริทึมที่เหมาะสมที่สุดในการแก้ในเวลา O(n) แบบเส้นตรงคือการใช้ Hash Table
แนวคิดคือสร้าง hash table ที่เก็บผลรวมของ subarray ทั้งหมดที่ผลรวมถูกเก็บเป็น Key และ index เป็น Value
เราจะวนลูปผ่านอาร์เรย์ทั้งหมดและเก็บผลรวมปัจจุบัน เราจะตรวจสอบว่าผลรวมปัจจุบันมีอยู่ใน hash table หรือไม่ หากมีอยู่ใน hashtable ให้อัปเดตความยาวสูงสุดของ subarray
- รับอินพุตขนาด N ของอาร์เรย์
- ฟังก์ชัน lenMax(int *arr, int size) รับอาร์เรย์และขนาดเป็นอินพุตซึ่งคืนค่าความยาวสูงสุดของ subarray ที่มีผลรวมเป็นศูนย์
- Unordered map ของจำนวนเต็มที่มี key เป็นผลรวมและ value เป็นดัชนี ตรวจสอบว่าผลรวมใดซ้ำหรือไม่
- วนลูปผ่านองค์ประกอบอาร์เรย์และหาผลรวมปัจจุบันของอาร์เรย์ ถ้าผลรวมมีอยู่ใน hashtable ให้หาความยาวสูงสุดของ subarray ถ้าไม่มี ให้แทรกลงใน hashtable พร้อมผลรวมใหม่และดัชนีของมัน
- คืนค่าความยาวสูงสุดเป็นเอาต์พุต
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size) {
unordered_map<int, int> mp;
int sum = 0;
int maxlen = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
if (arr[i] == 0 && maxlen == 0) {
maxlen = 1;
}
if (sum == 0) {
maxlen = i + 1;
}
if (mp.find(sum) != mp.end()) {
maxlen = max(maxlen, i - mp[sum]);
} else {
mp[sum] = i;
}
}
return maxlen;
}
int main() {
int N = 8;
int A[N] = {15, -2, 2, -8, 1, 7, 10, 23};
cout << lenMax(A, N) << endl;
return 0;
}
ผลลัพธ์
ถ้าเราจะรันโค้ดด้านบน จะพิมพ์เอาต์พุตเป็น
5
Subarray ที่ใหญ่ที่สุดที่มีผลรวม=0 คือ {-2, 2, -8, 1, 7} ดังนั้น ความยาวของ subarray ที่ใหญ่ที่สุดคือ '5'
