Millor Intercanvi. X77714

Un subvector d’un vector V és un tros del vector que va d’una posició i a una posició j (on $i \leq j$) i que conté els elements V[i], V[i+1], V[i+2], ... V[j]. Un subvector pot tenir una sola posició ($i = j$).

Sigui V un vector de naturals, no necessàriament ordenat. Aquest vector tindrà una mida de subvector màxim ordenat $M$ Ara bé, pot donar-se el cas que intercanviant dos element del vector, aquesta mida de subvector màxim ordenat, es vegi incrementada. Per exemple, si tenim el vector $V = [ 1, 3, 2, 5]$, la mida del subvector ordenat màxim serà $2$, bé pel subvector que va de la posició $0$ a la $1$, pel subvector que va la posició $2$ a la $3$. Ara bé, si intercanviem les posicions $1$ i $2$, ens queda el vector $V = [1 ,2 , 3, 5]$, que té un subvector ordenat de mida màxima $4$.

Fes la funció millor_intercanvi (V) tal que, donat un vector d’enters V, torni les dues posicions del vector i la mida del subvector ordenat més llarg que podem aconseguir amb un sol intercanvi d’aquestes dues posicions del vector (si no existissin, llavors $i = j = 0$).

Per exemple si el vector és $[1 , 3 , 2 , 7 , 5 , 2 , 3 , 1 , 8]$ la funció tornarà $4,7,5$ ja que és la mida del subvector ordenat que va de les posicions $4$ a $7$ després d’haver intercanviat les posicions $4$ i $7$.

Si tenim el vector $[2 , 3 , 4 , 7 , 5 , 9 , 3 , 1 , 8]$, la funció tornarà $3,4,6$, ja que és la mida del subvector ordenat més llarg, de les posicions $0$ fins a la $5$ després d’haver intercanviat les posicions $3$ i $4$.

Entrada

Un vector V d’enters.

Sortida

Les dues posicions del vector i la mida del subvector ordenat més llarg que podem aconseguir amb un sol intercanvi d’aquestes dues posicions del vector (si no existissin, llavors $i = j = 0$).