ho provato a risolvere fette di strudel così ma mi da 4 o 5 casi che sono in errore (nel senso prorpio sbagliato)
Si definisce il vettore di base che è la differenza tra
cannella e mandorle (vett[i]= cannella[i] – mandorle[i])
Si definisce poi il vettore delle somme prefisse (*)
Il vettore delle somme prefisse lo ordino tengo gli indici, vale a dire che nel vettore finale ci sono dei numeri corrispondenti agli indici che indicano appunto i valori in ordine crescenti presenti nel vettore somme prefisse.
Vale a dire, che se il vettore base era questo
0
1 2 3 4 5 indici
-7 2
10 3 0 -1
valori
il vettore somme prefisse sarà
0 1
2 3 4
5 6 indici
0 -7
-5 5 8 8 7 valori
E il vettore ordinato (che contiene indici dunque sarà)
0 1 2
3 4 5 indici
1 2
3 6 4 5 valori
Ora per trovare il pezzo più lungo basta trovare la più grossa differenza tra indici e lo fai in tempo lineare (se volete http://stackoverflow.com/questions/18956740/how-to-find-the-largest-difference-in-an-array )
Però la più lunga differenza tra y-x deve rispettare il criterio che la somma dei valori tra vett[y] e vett[x] compresi è >=0
Ed è qui che sorge il problema perché questa non è semplicemente somme prefisse[y] – somme prefisse[x] , no, è somme prefisse[y] – somme prefisse[x] + vett[y] , per come è definito il vettore somme prefisse. E così mi sorge il dubbio che sia sbagliato perché io vado appunto a ordinare il vettore delle somme prefisse, e non posso aggiungerci cose a mio piacimento dopo l’ordinamento.
Quindi o si definisce decentemente un vettore somme prefisse ( ma come???????) oppure si tiene testa a questa cosa ma veramente non mi viene in mente niente. Help?
(spero che abbiate capito circa come lo ho risolto). Ad ogni modo, sono sicuro che esistano altre soluzioni, ma mi piacerebbe tanto capire perché questa non va :) .
*Il vettore delle somme prefisse comunque lo definisco come
Somme[0]=0;
Somme[i]= somme[i-1] + vett[i-1];