Editorial for Kích thước mảng con lớn nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Độ 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
Comments