[C++, programare dinamică] Problema subsecvenței de produs maxim pe R

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Enunțul problemei
b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).

Pentru două rezolvări care se aplică doar asupra numerelor pozitive, sau respectiv doar asupra numerelor întregi, vedeți aici. Tot acolo găsiți intrări de test.

Cod sursă
Soluție inspirată de aici care funcționează în toate cazurile:
  • Nr. întregi: pozitive și negative.
  • Nr. cu virgulă: pozitive și negative.
  • Zero.
Și află și pozițiile de început și de sfârșit ale subsecvenței găsite.


float subsecv(float A[], int N,
       int &inceput, int &sfarsit)
{
       inceput = sfarsit = 1;
       int inceput_pozitiv_temp = 1,
              inceput_negativ_temp = 1;
       vector<float> p(N + 1, 0),
              n(N + 1, 0);
       int zero_index = 0;
       if (A[1] == 0)
       {
              p[1] = n[1] = 0;
              zero_index = 1;
       }
       else if (A[1] > 0)
       {
              p[1] = A[1];
              n[1] = 0;
       }
       else // A[1] < 0
       {
              p[1] = 0;
              n[1] = A[1];
       }
       float maximul = A[1];
       for (int i = 2; i <= N; ++i)
       {
              if (A[i] == 0)
              {
                     p[i] = n[i] = 0;
                     if (zero_index == 0)
                     {
                           zero_index = i;
                     }
              }
              else if (A[i] > 0)
              {
                     if (A[i] > A[i] * p[i - 1])
                     {
                           p[i] = A[i];
                           inceput_pozitiv_temp = i;
                     }
                     else
                     {
                           p[i] = A[i] * p[i - 1];
                     }
                     n[i] = A[i] * n[i - 1];
              }
              else // A[i] < 0
              {
                     p[i] = A[i] * n[i - 1];
                     inceput_pozitiv_temp = inceput_negativ_temp;
                     if (A[i] < A[i] * p[i - 1])
                     {
                           n[i] = A[i];
                           inceput_negativ_temp = i;
                     }
                     else
                     {
                           n[i] = A[i] * p[i - 1];
                           inceput_negativ_temp = inceput_pozitiv_temp;
                     }
              }
              if (p[i] > maximul)
              {
                     maximul = p[i];
                     inceput = inceput_pozitiv_temp;
                     sfarsit = i;
              }
       }
       if (maximul > 0)
       {
              return maximul;
       }
       if (zero_index != 0)
       {
              inceput = sfarsit = zero_index;
              return 0;
       }
       inceput = sfarsit = 1;
       return A[1];
}

Explicații
Dată fiind prima soluție de aici (titlul „Cod sursă”) se încearcă adaptarea ei pentru a funcționa și pentru numere negative și zero.

Dat fiind vectorul A cu indici de la 1 la N, lăsăm p[i] să fie produsul maxim pozitiv al unei subsecvențe din A[1, i] conținând A[i], și lăsăm pe n[i] să fie produsul minim negativ al unei asemenea subsecvențe. Dacă nici o asemenea subsecvență nu există, lăsăm p[i] = 0 sau n[i] = 0.

Inițializare:
  • dacă A[1] = 0, atunci p[1] = n[1] = 0
  • dacă A[1] > 0, atunci p[1] = A[1] și n[1] = 0
  • dacă A[1] < 0, atunci p[1] = 0 și n[1] = A[1]

Iterare:
  • dacă A[i] = 0, atunci p[i] = n[i] = 0
  • dacă A[i] > 0, atunci p[i] = max(A[i], A[i] * p[i - 1]) și n[i] = A[i] * n[i - 1]
  • dacă A[i] < 0, atunci p[i] = A[i] * n[i - 1] și n[i] = min(A[i], A[i] * P[i - 1])

Dacă max(p[1], ..., p[N]) > 0, atunci acesta este răspunsul. Unicul mod în care aceasta nu are loc este dacă nu există o subsecvență al cărei produs să fie pozitiv. Aceasta poate avea loc doar dacă vectorul conține doar numere negative și zerouri, și fiecare două numere negative sunt separate prin cel puțin un zero. Dacă există cel puțin un zero, atunci răspunsul este zero. Dacă nu există zerouri, atunci N = 1 și răspunsul este A[1].

Niciun comentariu:

Trimiteți un comentariu