Giả sử chúng ta đã cho một mảng N số nguyên có nhiệm vụ là tìm độ dài của mảng con có độ dài lớn nhất. Nếu không có bất kỳ mảng con nào có độ dài lớn nhất hoặc tổng bằng 0 thì trả về ‘0’. Ví dụ:
Đầu vào-1 -
N = 8
A[ ] = {15, -5, -1, 5,1, 4 } Đầu ra -
4
Giải thích - Mảng con lớn nhất có tổng bằng 0 là {-5, -1, 5, 1} có độ dài là 4.
Đầu vào-2 -
N = 5
A[ ] = {3, 2 ,4, 8, -1} Đầu ra -
0
Giải thích - Vì không có mảng con nào có tổng bằng 0 nên đầu ra là '0'.
Phương pháp tiếp cận để giải quyết vấn đề này
Có một số cách tiếp cận để giải quyết vấn đề cụ thể này. Thuật toán thích hợp nhất để giải trong thời gian tuyến tính O (n) là sử dụng Bảng băm.
Ý tưởng là tạo một bảng băm lưu trữ tổng của tất cả các mảng con có tổng được lưu trữ dưới dạng Khóa và chỉ mục dưới dạng Giá trị.
Đầu tiên chúng ta sẽ duyệt qua toàn bộ mảng và lưu trữ tổng hiện tại. Chúng tôi sẽ kiểm tra xem tổng hiện tại có sẵn trong bảng băm hay không. Nếu nó có trong bảng băm, thì hãy cập nhật độ dài tối đa của mảng con.
-
Lấy đầu vào kích thước N của mảng.
-
Một hàm lenMax (int * arr, int size) nhận một mảng và kích thước của nó làm đầu vào, trả về độ dài tối đa của mảng con chứa tổng bằng không.
-
Một bản đồ không có thứ tự các số nguyên có chứa khóa dưới dạng tổng và giá trị khi các chỉ mục kiểm tra xem có tổng nào lặp lại hay không.
-
Lặp lại phần tử mảng và tìm tổng hiện tại của mảng nếu tổng có trong bảng băm, sau đó tìm độ dài tối đa của mảng con. Nếu không, hãy chèn vào bảng băm với tổng mới và chỉ mục của nó.
-
Trả về độ dài tối đa dưới dạng đầu ra.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ in ra kết quả là,
5
Mảng con lớn nhất có sum =0 là {-2, 2, -8, 1, 7}. Do đó, độ dài của mảng con lớn nhất là ‘5’.