1299. Stefan [FZI_STEF]

Zadanie:
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.