Podciąg o największej wartości

Witam, mam do napisania program, który wyznacza podciąg liczb o największej wartości. W ciągu są same wartości dodatnie, jedyny problem to to, że jeśli drugi raz trafi się ta sama wartość to one się zerują na wzajem... Macie jakieś pomysły jak się za to zabrać?

A co jeżeli 3 razy?

Postaraj się dokładniej opisać zadanie, pozostawiłeś wiele niewiadomych. Rozumiem, że chodzi o ciągi liczbowe. Czy mają mieć jednakową długość? Co jeśli ta sama wartość trafi się 3, 4, 5 razy?

sorry macie rację..już piszę ;)
tak masz ciąg liczbowy, w którym niektóre liczby mogą się powtarzać dowolną ilość razy
Trzeba wybrać taki spójny podciąg, żeby jego suma była jak największa, natomiast jeśli jakaś liczba w nim wystąpi więcej niż raz to nie będzie sięliczyła jej wartość. Może wystąpić dwa razy może sto :D w każdym z tych przypadków te liczby nie będą się liczyć do sumy ;)
mam nadzieję, że już wiecie o co chodzi ;)

Myślałem o tym, żeby przejsc po kolei wszystkie elementy i dla każdego kolejnego wyznaczyć maksymalną sumę od początku do tego elementu, ale niestety tak nie wychodzi przez to zerowanie :D

Ja nie widzę innego sposobu niż brute-force, ale możliwe, że się da. Pamiętaj, że ciąg krótszy może być lepszym rozwiazaniem niż dłuższy (np 3 4 5 > 3 4 5 5)

taak, wiem
właśnie się zastanawiam, bo nie mam kompletnie pomysłu jaki algorytm by wykorzystać czy co

To jest zadanie z tego oi...
https://sio2.mimuw.edu.pl/c/oi22-1/p/kin/

jeszcze dzisiaj trwa (18h jeszcze), więc się wstrzymajcie chwilę

Po tym czasie mogę dać ewentualnie swoje rozwiązanie, które powinno być minimalnie szybsze od bruta.

@Edit Pn 16:54
jeszcze proszą o wstrzymanie się dzisiaj

wiem, ale ja nie biorę w tym udziału..i tak jestem za cienki ;p
jeszcze nie w tym roku :D
spoko to napisz jutro

Luźny pomysł zrodzony przy porannej kawie. Przepisujemy (z zachowaniem kolejności) do nowej tablicy tylko te liczby, które występują dokładnie raz. Szukamy w nowej tablicy spójnego podciągu o największej sumie.

Jako, że już po więc wrzucę swoje rozwiązanie, o którym wspomniałem wcześniej. Nie dużo lepsze od bruta, ale zawsze coś. Może komuś da jakiś pomysł na coś jeszcze lepszego.

#include <iostream>

using namespace std;

int main()
{
    int n, m; //1 <= m <= n <= 1 000 000
    cin >> n >> m;
    int* films = new int[n];
    int* coolness = new int[m];
    int* numberOfOccurences = new int[m];
    int* firstOccurence = new int[m];
    for(int i = 0; i < n; ++i)
    {
        cin >> films[i];
        films[i] -= 1;
    }
    for(int i = 0; i < m;++i)
    {
        cin >> coolness[i]; // 1 <= coolness <= 1 000 000
    }
    uint64_t maxResult = 0;
    int first = 0;
    while(first < n)
    {
        for(int i = 0; i < m; ++i) numberOfOccurences[i] = 0;
        for(int i = 0; i < m; ++i) firstOccurence[i] = 0;
        uint64_t result = 0;
        int firstRepeated = -1;
        for(int i = first; i < n; ++i)
        {
            int& occ = numberOfOccurences[films[i]];
            ++occ;
            if(occ == 1)
            {
                result += coolness[films[i]];
                firstOccurence[films[i]] = i;
            }
            else if(occ == 2)
            {
                result -= coolness[films[i]];
                if(firstOccurence[films[i]] < firstOccurence[firstRepeated]) firstRepeated = films[i];
            }

            if(result > maxResult) maxResult = result;
        }
        if(firstRepeated == -1) break;
        first = firstOccurence[firstRepeated]+1;
    }

    cout << maxResult;
    return 0;
}

Polega to na tym, że sprawdzam od początku do końca (Trzymając największą wartość jaką udało nam się osiągnąć w dowolnej chwili), ale nie dla wszystkich możliwych początków.
Tj. trzymam sobie dla każdej iteracji tablicę, w której trzymam informację kiedy jest pierwsze wystąpienie danego filmu.
Wtedy w każdym miejscu, gdzie film powtarza się po raz pierwszy (występuje po raz drugi) sprawdzam, czy jest jakiś inny, który już się powtórzył, i którego pierwsze wystąpienie jest pierwsze.
Efektywnie dostaję pozycję najwcześniejszego elementu, który kiedykolwiek się powtórzył.
Po co nam ona? Możemy wtedy przeskoczyć trochę.

Czyli na przykład:
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

Mamy filmy 2 3 1 ...
Pierwsza iteracja jest po wszystkich.
W niej zauważamy, że pierwszym elementem jaki się później powtarza jest 1
Możemy pominąć więc 3, bo pierwszym filmem jaki mógł zepsuć zadowolenie jest film o numerze 1. Eliminując pierwszą jedynkę MOŻEMY sprawić, że dalej albo wystąpi tylko jedna, albo po dotarciu do drugiej będzie lepsza suma. Może nie musi. Jest to zależnie od przypadku.
Lecimy po 1 4 1 2 4 1
Dalej znowu 1. Tym razem nic nie pominiemy.
4 1 2 4 1
teraz 4
1 2 4 1
teraz 1
2 4 1

pomijamy 4 przypadki z 9

Dla innego przykładu

10 5
2 4 1 1 2 3 2 2 2 3
14 7 13 16 10

Sprawdzamy 'tylko' te możliwości

2 4 1 1 2 3 2 2 2 3
  4 1 1 2 3 2 2 2 3
      1 2 3 2 2 2 3
          3 2 2 2 3
            2 2 2 3
              2 2 3
                2 3

pomijamy 3 przypadki z 10
Algorytm jest wysoko zależny od występujących filmów. Działa lepiej kiedy powtórzeń jest mało, lub są daleko od siebie (np dla testu ocen3 działa(łby) ~10 razy szybciej niż brute, tam wszystkie wartości są inne, tylko jedna się powtarza co 10)
Dla jednych danych działa lepiej, dla drugich może być wolniejszy od brute forca, ale myślę, że powinien lepiej się zachowywać w ogólnym przypadku.