https://pl.spoj.com/problems/FZI_STEF
Skrócony opis problemu:
Dla podanego ciągu $n$ liczb należy znaleźć podłańcuch o maksymalnej sumie.
Dla przypomnienia, podłańcuch to spójny podciąg.
Gdybyśmy mieli do znalezienia podciąg o maksymalnej sumie to wynikiem byłaby po prostu suma wszystkich liczb dodatnich.
Rozwiązanie naiwne:
Możemy znaleźć wszystkie podłańcuchy, obliczyć ich sumy i na koniec wypisać największą z nich.
Jak znaleźć wszystkie podłańcuchy? Ano na przykład tak, że bierzemy sobie wszystkie możliwe pary pozycji (również pozycje w parze same ze sobą) i te pary wyznaczają nam końce podłańcuchów. Dla każdego z nich liczymy ich sumę i wypisujemy największą z nich.
Złożoność: $O(n^3)$, bo mamy $\frac{n(n-1)}{2}$ par i dla każdej obliczamy sumę w pesymistycznym czasie $O(n)$.
Algorytm:
int main()
{
int i, j, k, x, max = 0, tab[t];
get(t);
for(i = 0; i < t; ++i)
get(tab[i]);
for(i = 0; i < t; ++i)
for(j = i; j < t; ++j)
{
for(x = 0, k = i; k <= j; ++k)
x += tab[k];
if(x > max)
max = x;
}
print(max);
}
Rozwiązanie sprytniejsze:
Możemy przyspieszyć powyższe rozwiązanie, szybciej zliczając sumy. Skorzystamy tutaj z sum prefiksowych.
Sumy prefiksowe to sumy wszystkich wyrazów ciągu od jego początku. A więc dla ciągu: 1 2 3 sumy prefiksowe to: 1 3 6.
Sumy prefiksowe możemy obliczyć w czasie liniowym. Iterujemy po prostu do tablicy i do poprzedniej sumy prefiksowej dodajemy nowy element.
Po co nam one? Ano po to, że dzięki nim możemy obliczyć sumę dowolnego podłańcucha o końcach w $a$ i $b$ w czasie stałym. Jak? Ano tak, że bierzemy $tab[b]$ i odejmujemy od niego $tab[a-1]$ (lub jeśli $a=0$ nic nie odejmujemy). Działa to dlatego, że $tab[b]$ jest sumą wyrazów od początku do pozycji $b$. Musimy się zatem pozbyć sumy elementów przed pozycją $a$, a więc $tab[a-1]$.
Złożoność: $O(n^2)$, gdyż dla każdego z $\frac{n(n-1)}{2}$ podłańcuchów obliczamy jego sumę w czasie stałym.
Algorytm:
int main()
{
int t, i, j, k, x, max = 0, tab[t];
get(t);
for(i = 0; i < t; ++i)
{
get(tab[i]);
if(i > 0)
tab[i] += tab[i-1]; // w tab będą teraz sumy prefiksowe; same elementy nie są nam już potrzebne
}
for(i = 0; i < t; ++i)
for(j = i; j < t; ++j)
{
x = tab[j];
if(i > 0)
x -= tab[i];
if(x > max)
max = x;
}
print(max);
}
Rozwiązanie sprytniejsze nr 2:
Rozwiązanie to jest podobne do poprzedniego. Tu również będziemy zliczać sumy w czasie stałym, ale tym razem inaczej. Na bieżąco.
Zauważmy, że sprawdzamy podłańcuchy w takiej kolejności (dla $n=4$, indeksujemy od 0): 0-0, 0-1, 0-2, 0-3, 1-1, 1-2, 1-3, 2-2, 2-3, 3-3. Dla pierwszej pary potrzebujemy tylko pierwszego elementu. Następnie pierwszych dwóch, potem pierwszych trzech. Itd. Możemy więc na bieżąco dodawać tylko jeden element do sumy i gdy przejdziemy wszystkie podłańcuchy dla danej pozycji startowej, to będziemy zerować naszą sumę.
Złożoność: $O(n^2)$.
Algorytm:
int main()
{
int t, i, j, k, x, max = 0, tab[t];
get(t);
for(i = 0; i < t; ++i)
get(tab[i]);
for(i = 0; i < t; ++i)
for(x = 0, j = i; j < t; ++j) // zerujemy sumę
{
x += tab[j]; // dodajemy najnowszy element do sumy
if(x > max)
max = x;
}
print(max);
}
Rozwiązanie jeszcze sprytniejsze:
Do rozwiązania tego problemu możemy również użyć metody "dziel i zwyciężaj".
Polega ona na tym, że dzielimy problem na mniejsze (często 2), a następnie obliczamy dla nich rekurencyjnie wyniki schodząc do coraz mniejszych danych, aż osiągnie się skrajnie małe dane, dla których można obliczyć wynik w czasie stałym. A następnie mając te [często 2] wyniki pośrednie łączy się je w jeden, ostateczny wynik.
Tak więc w tym przypadku, podzielimy sobie tablicę naszych elementów na 2 części i znajdziemy rekurencyjnie podłańcuch o największej sumie dla każdego z nich, a następnie wybierzemy większy z nich. Wystarczy? Nie. Może się bowiem zdarzyć, że podłańcuch o największej sumie będzie przebiegał przez miejsce naszego podziału. Taką sytuację też musimy wziąć pod uwagę. Tak więc de facto wynikiem będzie maksimum z wyniku z lewej części ciągu, prawej oraz największej sumy przechodzącej przez miejsce podziału.
Pierwsze 2 wyniki obliczamy rekurencyjnie. Nie ma w tym żadnej filozofii, jak zobaczycie w poniższym kodzie. Jak jednak znajdywać podłańcuch o największej sumie przechodzący przez miejsce podziału $m$? Ano tak, że sprawdzamy wszystkie łańcuchy od $m$ do początku ciągu z naszego wywołania rekurencyjnego (czyli w lewo) i bierzemy z tego największą sumę $x$ oraz sprawdzamy wszystkie łańcuchy od $m+1$ do końca ciągu z naszego wywołania rekurencyjnego (czyli w prawo) i bierzemy z tego największą sumę $y$. Na koniec łączymy oba wyniki w $x+y$ i to jest nasz trzeci wynik pośredni, który porównujemy z dwoma poprzednimi i wybieramy największy.
Np. dla ciągu: -2 -5 6 -2 -3 1 6 -5 najpierw dzielimy go na podciągi: -2 -5 6 -2 oraz -3 1 6 -5, następnie znajdujemy rekurencyjnie dla obu wyniki pośrednie. Odpowiednio: 6 i 7. A następnie szukamy trzeciego wyniku, biorąc za $m$ -2 albo -3. Ja wezmę -3, bo jestem za prawicą. Tak więc idziemy od -3 w lewo i obliczamy kolejne sumy (wszystkie muszą kończyć się na -3). Są to: -3, -5, 1, -4, -6. Bierzemy z nich maxa, czyli 1. Teraz zaczynamy od elementu następującym po -3, czyli od 1. Kolejne sumy [idąc w prawo] to: 1, 7, 2. Maxem jest 7. Łączymy te sumy i wychodzi nam, że trzeci wynik pośredni to 1+7=8. Bierzemy maxa z tych trzech: 6, 7, 8. Ostateczny wynik to zatem 8.
Złożoność: $O(n \log n)$. Ale skąd się tam wziął logarytm? Przecież nie sortujemy niczego, nie wyszukujemy niczego binarnie, nie używamy seta, itd. Złożoność ta wzięła się z rozwiązania poniższego równania rekurencyjnego:
$$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$$
Wykonujemy bowiem 2 wywołania rekurencyjne, ale dla połowy poprzednich danych oraz dodatkowo liczenie dodatkowego wyniku pośredniego w czasie liniowym.
Jak się rozwiązuje równania rekurencyjne?
- równania typu "dziel i rządź" lub "dziel i zwyciężaj"
$$T(n) = \begin{cases} c, &\text{gdy } n = 1 \\ a \cdot T\left(\frac{n}{b}\right) + d(n), &\text{gdy } n = b^k \end{cases}$$
..którego rozwiązanie to:
$$T(n) = \begin{cases} \Theta\left(n^{log_b d(b)}\right), &\text{gdy } a < d(b) \\ \Theta\left(n^{log_b a} log n\right), &\text{gdy } a = d(b) \\ \Theta\left(n^{log_b a}\right), &\text{gdy } a > d(b) \end{cases}$$ - równania typu "jeden krok w tył"
$$T(n) = \begin{cases} c, &\text{gdy } n = 0 \\ a \cdot T(n-1) + d(n), &\text{gdy } n > 0 \end{cases}$$
...którego rozwiązanie to:
$$T(n) = \begin{cases} \Theta\left(a^n\right), &\text{gdy } d(n) = O\left(\frac{a^n}{n^\varepsilon}\right), \varepsilon > 1 \\ O\left(n \cdot a^n\right), &\text{gdy } d(n) = O\left(a^n\right) \\ O\left(n \cdot d(n)\right), &\text{gdy } d(n) = \omega\left(a^n\right) \end{cases}$$
Algorytm:
int crossing(int l, int m, int r)
{
int s = 0, s1 = -2e9, s2 = -2e9, i;
for(i = m; i >= l; --i)
{
s += tab[i];
if(s > s1)
s1 = s;
}
s = 0; // zerujemy s
for(i = m+1; i <= r; ++i)
{
s += tab[i];
if(s > s2)
s2 = s;
}
return s1+s2;
}
int half(int l, int r)
{
if(l == r) // skrajny warunek
return tab[r];
int m = (l+r)/2;
return max(half(l, m), half(m+1, r), crossing(l, m, r), 0); // bierzemy maxa z 3 wyników pośrednich i zera, żeby wynik nie był ujemny
}
int main()
{
int t, i, tab[t];
get(t);
for(i = 0; i < t; ++i)
get(tab[i]);
print(half(0, t-1));
}
Rozwiązanie najsprytniejsze:
Możemy do problemu podejść również zachłannie. Powiedzmy, że na jakimś etapie $i$ mamy największą możliwą do uzyskania sumę, która kończy się na elemencie $tab[i]$ (nazwijmy ją $w_i$). Wtedy jeśli weźmiemy nowy element i chcemy dla niego obliczyć $w_{i+1}$ to będzie on równy $w_i+tab[i+1]$ jeśli $w_i > 0$ lub $tab[i+1]$ w przeciwnym wypadku. Dlaczego? Bo jeśli największa możliwa suma po lewej stronie będzie ujemna, to nie opłaca jej się brać pod uwagę. Po każdym rozpatrzeniu elementu aktualizujemy końcowy wynik sprawdzając czy $w_i$ nie jest przypadkiem od niego większa.
Możemy zauważyć też, że skoro do obliczenia $w_{i+1}$ potrzebujemy tylko $w_i$ i $a_{i+1}$ to nie potrzebujemy tablicować ani $w$ ani $tab$, gdyż bierzemy tylko ostatnią wartość.
Złożoność: $O(n)$, gdyż przechodzimy wszystkie elementy tylko raz i dla każdego z nich wykonujemy tylko kilka porównań i przypisać. Należy też zwrócić uwagę, że jest to również najlepsze rozwiązanie pod względem złożoności pamięciowej, która wynosi $O(1)$, a wynosiła zawsze $O(n)$.
Ostateczny algorytm:
int main()
{
int t, w = 0, s = 0, x;
get(t);
while(t--)
{
get(x);
if(w > 0)
w += x;
else
w = x;
if(w > s)
s = w;
}
print(s);
}
Uwaga: Być może zainteresuje Cię wariant dwuwymiarowy tego problemu, opisany tutaj.
To jest łatwe zadanie?
OdpowiedzUsuń