Pagini recente » Cod sursa (job #2555363) | Cod sursa (job #812611) | Cod sursa (job #894802) | Cod sursa (job #245203) | Cod sursa (job #3182572)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int nmax = 100003;
stack <int> st;
int main(){
int i = 1, j, n, dp[2][nmax], predecesori[nmax], maxim = -1, maxPoz;
fin>>n;
fin>>dp[0][1];
dp[1][1] = 1;
predecesori[1] = 0;
for(i = 2; i <= n; i++){
fin>>dp[0][i];
dp[1][i] = 0;
for(j = i - 1; j >= 1; j--)
if(dp[0][i] > dp[0][j]){
//dp[1][i] = max(dp[1][i], dp[1][j]);
if(dp[1][i] < dp[1][j]){
predecesori[i] = j;
dp[1][i] = dp[1][j];
}
//cout<<"pt i = "<<i<<", j = "<<j<<", dp[0][j] = "<<dp[0][j]<<"\n";
}
dp[1][i]++;
if(dp[1][i] > maxim){
maxim = dp[1][i];
maxPoz = i;
}
}
/*for(i = 1; i <= n; i++)
fout<<dp[0][i]<<" "<<dp[1][i]<<"\n";
for(i = 1; i <= n; i++)
fout<<predecesori[i]<<"\n";*/
fout<<maxim<<"\n";
st.push(dp[0][maxPoz]);
while(predecesori[maxPoz]){
st.push(dp[0][predecesori[maxPoz]]);
maxPoz = predecesori[maxPoz];
}
while(!st.empty()){
fout<<st.top()<<" ";
st.pop();
}
}