30/09/2018, 19:54
Cho em hỏi cách tính tổng dãy số liên tiếp bằng 0 mà chỉ n log n
Em làm bài này ok nhưng n^2. Bài này em làm một mảng tổng dồn, sau đó
for (int i=1; i<=n; i++)
for (int j=1; j<i; j<=n; j++)
if (a[i]-a[j-1]==0) cập nhật res=max(res, i-j+1);
Nhưng em làm vậy là n^2 rồi. Cho em hỏi còn cách nào nhanh hơn không ạ? Em muốn là n log n ạ. Em cám ơn
Bài liên quan
s[i]=s[j]; vì s[j]= s[i]+ sum(a[x] với x từ i->j). như vậy bài toán trở thành đếm số cặp = nhau của dãy s. Chỉ cần sort và đếm là đượcem cám ơn anh nhiều :)))
Dùng thêm unordered_map thì chỉ còn O(n)