Pagini recente » Cod sursa (job #3040791) | Cod sursa (job #150985) | Cod sursa (job #1602258) | Cod sursa (job #1218618) | Cod sursa (job #1999546)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int v[100001], n; //date de intrare
int lgSecv[100001];//lgSecv[i] - lungimea secveentei care se termina in v[i];
int rezultat[100001];//array cu solutia finala
int poz;
void citire(){
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i];
}
void rezolvare(){
for(int i = n; i >= 1; i--){
lgSecv[i] = 1;
for(int j = i + 1; j <= n; j++)
if(v[i] < v[j] && lgSecv[i] < lgSecv[j] + 1)
lgSecv[i] = lgSecv[j] + 1;
}
int LgMinima = n + 1;
for(int i =1; i<=n; i++){
bool ok = true;
for(int j = i - 1; j >= 1; j--)
if(v[j] < v[i] && lgSecv[i] + 1 == lgSecv[j]){
ok = false;
break;
}
if(ok == true && LgMinima > lgSecv[i]){
LgMinima = lgSecv[i];
poz = i;
}
}
if(LgMinima == n + 1){
LgMinima = 1;
poz = 1;
}
int L = LgMinima;
int plec = poz;
int aux = 0;
while(L != 0){
aux = 0;
for(int i = plec; i <= n; i++){
if(aux == 0 && L == lgSecv[i]){
aux = plec = i;
}
if(L == lgSecv[i] && v[i] < v[aux])
plec = i;
}
rezultat[++rezultat[0]] = plec;
L -- ;
}
out << LgMinima << '\n';
for(int i = 1; i <= rezultat[0]; i++)
out << rezultat[i] << ' ';
}
int main(){
citire();
rezolvare();
return 0;
}