Hướng dẫn cho Kích thước mảng con lớn nhất
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Độ phức tạp O(nlogn)
Đương nhiên, mảng con cần tìm sẽ có kích thước trong [1,n]
Vì mọi phần tử đều >0 nên ta thấy, giá trị các phần tử thuộc mảng cộng dồn sẽ tăng dần.
Tức là,
nếu $a[i]+a[i+1]+...+a[j-1]+a[j]≤K $
thì \(a[i]+a[i+1]+...+a[j-1]≤K\) với \(a[j]>0\)
Ta tìm kiếm nhị phân trong đoạn 1,n để tìm dãy con có kích thước lớn nhất sao cho mọi dãy con đó có kích thước đó có tổng ≤K
Bình luận