Millor Intercanvi. X24267

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 V[1:2] o pel subvector V[3:4]. Ara bé, si intercanviem les posicions $2$ i $3$, 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 = 1$).

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

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

Entrada

Un vector V d’enters.

Sortida

Un vector amb (en aquest ordre) les dues posicions de V i la mida del subvector de V ordenat més llarg que podem aconseguir amb un sol intercanvi d’aquestes dues posicions del vector (si no existissin, llavors $i = j = 1$).