Przedzial zawierajacy max liczb podzielnych przez 3.

Czesc. Mam takie zadanie:

"Danych jest n liczb. Znalezc taki przedzial, ktory zawiera najwieksza ilosc liczb z tego zbioru podzielnych przez 3. Dlugosc przedzialu pobrac od uzytkownika."

Wynik powinien byc postaci [poczatek;poczatek+dlugosc], gdzie poczatek to jedna z liczb zbioru.

Np. majac jakis taki zbior i szukana dlugosc przedzialu = 25
15,9,2,8,1,3,30,33,36,39

Wynikiem powinien byc przedzial [30;55].

Ja sobie posortowalem najpierw te punkty i pozniej przechadzac po posortowanej tablicy dla kazdego poczatku przedzialu szukalem liczb podzielnych przez 3 nalezacych do przedzialu [poczatek;poczatek+25]. Ale przy malej rozbieznosci wartosci danych i dlugim przedziale robi mi sie z tego chyba nawet O(n^2). Da sie to zrobic szybciej?

Zapomnialem dodac ze zakladamy, ze w danych zbiorze liczb zadne liczby sie nie powtarzaja.

A dlaczego wynikiem nie jest przedział [15;40]?
Spróbuj tak:

• przepisz do nowej tablicy liczby podzielne przez 3 15,9,3,30,39,33,36,39,
• posortuj 3,9,15,30,33,36,39,
• utwórz nową tablicę z różnic 6,6,15,3,3,3
• znajdź najdłuższy podciąg o sumie <= od podanej liczby http://e2718281828459045.wordpress.com/2013/08/19/longest-subarray-whose-sum-k/
  Ostatnia operacja ma złożoność O(n*log(n)), złożoność sortowania zależy od wybranego algorytmu, pozostałe operacje mają mają złożoność O(n).