สมมติว่าเราได้ให้อาร์เรย์ของจำนวนเต็ม N ที่มีหน้าที่ค้นหาความยาวของอาร์เรย์ย่อยที่มีความยาวสูงสุด หากไม่มีอาร์เรย์ย่อยใดๆ ที่มีความยาวสูงสุดหรือผลรวมเท่ากับ 0 ให้คืนค่า '0' ตัวอย่างเช่น
อินพุต-1 −
N = 8
A[ ] = {15, -5, -1, 5,1, 4 } ผลผลิต −
4
คำอธิบาย − อาร์เรย์ย่อยที่ใหญ่ที่สุดที่มีค่าผลรวมเป็นศูนย์คือ { -5, -1, 5, 1} ซึ่งมีความยาวเท่ากับ 4
อินพุต-2 −
N = 5
A[ ] = {3, 2 ,4, 8, -1} ผลผลิต −
0
คำอธิบาย − เนื่องจากไม่มีอาร์เรย์ย่อยที่มีผลรวมเท่ากับศูนย์ เอาต์พุตจึงเป็น '0'
แนวทางการแก้ปัญหานี้
มีหลายวิธีในการแก้ปัญหานี้โดยเฉพาะ อัลกอริทึมที่เหมาะสมที่สุดในการแก้ปัญหาในเวลาเชิงเส้น O(n) คือการใช้ตารางแฮช
แนวคิดคือการสร้างตารางแฮชที่เก็บผลรวมของอาร์เรย์ย่อยทั้งหมดที่มีการจัดเก็บผลรวมเป็นคีย์และดัชนีเป็นค่า
ก่อนอื่นเราจะสำรวจทั้งอาร์เรย์และเก็บผลรวมปัจจุบัน เราจะตรวจสอบว่าผลรวมปัจจุบันมีอยู่ในตารางแฮชหรือไม่ หากมีอยู่ในตารางแฮช ให้อัปเดตความยาวสูงสุดของอาร์เรย์ย่อย
-
รับอินพุตขนาด N ของอาร์เรย์
-
ฟังก์ชัน lenMax(int *arr, int size) รับอาร์เรย์และขนาดของอาร์เรย์เป็นอินพุต ซึ่งจะคืนค่าความยาวสูงสุดของอาร์เรย์ย่อยที่มีผลรวมเป็นศูนย์
-
แผนที่แบบไม่เรียงลำดับของจำนวนเต็มที่มีคีย์เป็นผลรวมและค่าในขณะที่ดัชนีตรวจสอบว่าผลรวมใด ๆ เกิดขึ้นซ้ำหรือไม่
-
วนซ้ำองค์ประกอบอาร์เรย์และค้นหาผลรวมปัจจุบันของอาร์เรย์หากผลรวมมีอยู่ใน 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=6;
int A[N]={15,-2,2,-8,1,7,10,23};
cout<<lenMax(A,N)<<endl;
return 0;
} ผลลัพธ์
หากเราจะเรียกใช้โค้ดข้างต้น มันจะพิมพ์ผลลัพธ์เป็น,
5
อาร์เรย์ย่อยที่ใหญ่ที่สุดที่มีผลรวม=0 คือ {-2, 2, -8, 1, 7} ดังนั้น ความยาวของอาร์เรย์ย่อยที่ใหญ่ที่สุดคือ '5'
