Pagini recente » Cod sursa (job #2663886) | Cod sursa (job #2275518) | Cod sursa (job #694161) | Cod sursa (job #2325031) | Cod sursa (job #1043140)
#include <fstream>
using namespace std;
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
const int nmax = 5002;
int n;
int a[nmax], dp[nmax], who[nmax];
void readData() {
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
}
void solve() {
int bstPos = n;
for (int i = n;i >= 1;i--) {
who[i] = i;
dp[i] = 1;
for(int j = i + 1;j <= n;j++) {
if (a[j] > a[i] && (dp[j] + 1 > dp[i] || (dp[i] == dp[j] + 1 && a[j] < a[who[i]])) ) {
who[i] = j;
dp[i] = dp[j] + 1;
}
}
if (dp[i] > dp[bstPos] || (dp[i] == dp[bstPos] && a[i] < a[bstPos])) {
bstPos = i;
}
}
cout << dp[bstPos] << "\n";
while (bstPos != who[bstPos]) {
cout << bstPos << " ";
bstPos = who[bstPos];
}
cout << bstPos;
}
int main()
{
readData();
solve();
return 0;
}