algoritm pt produs maxim. help!

[spank]

caut un algoritm pt aflarea subsirului de produs maxim dintr-un sir. numerele pot fi si negative.
ma gandesc la un algoritm eficient, pt ca un algoritm cu complexitate mare cred ca pot elabora si eu.

multumesc!

[•Cosmin]

Sa nu fie tema problema asta ca ar fi nasol sa iti facem tema de casa.

E clar ca daca apare numarul 0 sau un numar subunitar nu vrei sa il incluzi in produs, in rest bagi toate numerele. Daca rezultatul e negativ atunci elimini cel mai mic numar negativ din solutie, daca nu returnezi solutia.

[spank]

pai nu neaparat.. prod a doua numere negative e pozitiv. spre ex.

0.7 10 -1 17 -19 0.1 100 0.9

subsirul maxim e cel bolduit.
se respecta ordinea sirului introdus

[•Cosmin]

daca elimini 0.1 scoti un rezultat mai mare ...

[•bogdan2412]

Tu vrei subsecventa sau subsir?... Subsirul nu are elemente consecutive neaparat, spre deosebire de secventa

Daca vrei secventa, exista problema Secventa 4 (secv4), cu solutia aici.

[•wefgef]

Sa nu fie tema problema asta ca ar fi nasol sa iti facem tema de casa.

E clar ca daca apare numarul 0 sau un numar subunitar nu vrei sa il incluzi in produs, in rest bagi toate numerele. Daca rezultatul e negativ atunci elimini cel mai mic numar negativ din solutie, daca nu returnezi solutia.

Elimini cel mai mare numar negativ (cel mai mic in modul ).

Ai cazuri particulare cand nu ai numere supraunitare in modul, sau cand ai unul singur care e negativ. In aceste cazuri alegi maximul din sir.

[spank]

da... exact problema cu secventa vreau sa o rezolv.
x si y intre ce valori variaza ? nu prea am inteles treaba cu intervalul respectiv

[•cosminp]

 uite o solutzie:
 
 Obs: - daca n>=2 (nr. de elem.) produsul maxim va fi >=0

[•cos_min]

da ii adevarat. da la ce te ajuta ? 

[•cosminp]

   - daca 0 se afla in sir  atunci va fi suficient sa rezolvam pb pt subsirul din dreapta lui 0 si cel din stanga lui si in final sa retzinem optimul

  In cele ce urmeaza voi rezolva pb in cazul in care nu se afla nici un zero in sir.
 
  Fie p=a[1]*a[2]*...*a ,  p[0]=1.  Pentru fiecare i voi dori sa caut secventza optima ce se termina la pozitzia i. Sa presupunem ca aceasta incepe la pozitia j. Atunci produsul va fi p/p[j-1] care trebuie sa fie maxim.
        - daca p>0 atunci p[j-1] va trebui sa fie cea mai mica valoare pozitiva din stanga lui i;
        - daca p<0 atunci p[j-1] va trebui sa fie cea mai mare valoare negativa din stanga lui i;

Cu alte cuvinte parcurgem sirul de la inceput catre sfarsit si retzinem in doua variabile cele doua valori de mai sus pana in momentul i, determinam secventza de produs maxim ce se termina in pozitzia i si o retzinem daca e optima, apoi refacem cele doua variabile...

E posibil ca produsele p sa fie fff mari. Se vor logaritma numerele in modul  din sirul initzial si se vor retzine sumele partziale ale  acestora intr-un vector s, unde s=log(|p|)  si in loc de produsul optim vom retzine logaritmul acestuia si pozitziile de inceput si sfarsit ; acum va trebui sa comparam log(p/p[j-1])=s-s[j-1] cu val optima.  Complexitatea este de O(n).

 
 

[•cosminp]

trebuia sa imi apara mai sus si niste indici ...

[spank]

am facut urm program

#include<stdio.h>
#include<stdlib.h>

float prod(float*,int);

int main()
{
    int n,i;
    float *a;
   
    printf("n=");
    scanf("%d",&n);
    a=calloc(n,sizeof(float));
    for(i=0;i<n;i++)
    {
              printf("a[%d]=",i);
              scanf("%f",&a);
    }
    printf("%f\n",prod(a,n));
    free(a);
    system("PAUSE");
   
    return 0;
}     

float prod(float *a, int n)
{
    int i,j;
    float *b=calloc(n,sizeof(int)),p=0;

    b[0]=a[0];
    for(i=1;i<n;i++) b=b[i-1]*a;
    for(i=1;i<n;i++)
    for(j=0;j<i;j++) if(p<b/b[j]) p=b/b[j];
    return p;
}

complexitatea cred ca este cam O(n.log(n)). Nu am inteles ideea sa fac in O(n). Puteti sa fiti mai expliciti?
Stiu ca nu am considerat in program toate cazurile posibile, ma intereseaza doar algoritmul.

Multumesc!

[•cos_min]

programul tau nu are O(n*logn) ii aproximativ O(n^2)

[spank]

incercam si eu sa ma laud. o explicatie mai detaliata despre cum sa`l fac O(n) avetzi ?

[•pauldb]

Logaritmezi toate valorile. Folosind formula log (a*b) = log a + log b, problema se reduce la aflarea secventei de suma maxima (care este o problema clasica). Daca vrei sa-ti explic si cum se face asta, trimite-mi un PM.

[•azotlichid]

si cum logaritmezi tu un numar negativ?

[•pauldb]

N-am vazut ca erau si numere negative. Atunci faci ca la secv4  cu mici modificari.

[•silviug]

Problema ne-a fost propusa spre rezolvare la primul lab de Analiza Algoritmilor (in UPB). Probabil spank e si el anul trei la noi si avea nevoie de ajutor. Daca e asa, e foarte bine ca v-a cerut ajutorul desi corect ar fi fost sa mentioneze ca e tema. Enuntul exact suna asa: "Se da un sir de N numere intregi (N <= 10^6). Sa se afle subsecventa (i.e., subset de elemente pe pozitii consecutive) de produs maxim. Sirul poate fi citit o singura data si se cere solutie care foloseste memorie O(1) (i.e., sirul nu poate fi incarcat in memorie)".

Eu stiu cum se rezolva, dar las mai tinerele minti ale patriei sa gaseasca solutia

Have fun,

Silviu

[•byndrsn]

la prima vedere, nu pare prea important ca numerele sunt intregi.. pot sa fie chiar reale (cam acelasi algoritm, poate un pic mai simplu)..
asa ca sa zicem ca-s reale..

daca numerele sunt toate pozitive, poti aplica algoritmul pentru subsecventza de suma maxima (fiind reale, pot sa fie < 1: o subsecventza cu 0 elemente are produsul 1, ignori subsecventze cu produs < 1)

fie prod(s) = produsul elementelor subsecventzei s

tii doua subsecventze (de fapt tii modulul produsului numerelor si eventual cei 2 indici): prima este subsecventza maximala cu produs pozitiv (prod(s) > 0, si pentru orice subsecventza s' cu prod(s') > 0: prod(s) >= prod(s'))
cea de-a doua este subsecventza maximala cu produs negativ (prod(s) < 0,
si pentru orice subsecventza s' cu prod(s') < 0: |prod(s)| >= |prod(s')|)

sa zicem ca o subsecventza maximala e x[ i ]..x[ j ]
daca x[ j ] > 0:  x[ i ] .. x[ j-1 ] este o subsecventza maximala cu produs pozitiv
daca x[ j ] < 0:  x[ i ] .. x[ j-1 ] este o subsecventza maximala cu produs negativ

fie A produsul subsecventzei maximale cu produs pozitiv, B valoarea absoluta a produsului subsecventzei maximale cu produs negativ

initial A = 1; B = 0

deci faci update cam asa:
   citesti x[ i ]
   
   x[ i ] > 0: A *= x[ i ]; B *= x[ i ]
   x[ i ] < 0: A *= abs(x[ i ]); B *= abs(x[ i ]); swap A si B
   x[ i ] = 0: A = 1; B = 0
   
   A = max(1, A);
   best = max(best, A);

ai nevoie sa tii doar 3 variabile (A, B, best) si eventual cate o pereche de indici pentru fiecare (daca ai nevoie sa stii indicii de inceput si sfarsit ai subsecventzei)

trebuie sa demonstrezi ca e corect? inductie.