Pagini recente » Cod sursa (job #2771798) | Cod sursa (job #702770) | Cod sursa (job #1100993) | Cod sursa (job #888361) | Cod sursa (job #1729978)
#include <iostream>
#include <fstream>
using namespace std;
const int Nmax = 255;
int dataString[Nmax];
int best[Nmax];
int sol[Nmax];
int pre[Nmax];
int n;
int lastindex;
int maxindex;
void readData(char* fileName);
void writeData(char* fileName);
void initData();
void doDynamic();
void doSol();
int main()
{
char* fileToRead = "scmax.in";
char* fileToWrite = "scmax.out";
initData();
readData(fileToRead);
doDynamic();
doSol();
writeData(fileToWrite);
return 0;
}
void readData(char* fileName)
{
ifstream inFile (fileName);
inFile >> n;
for(int i=0; i<n; i++)
{
inFile >> dataString[i];
}
inFile.close();
}
void initData()
{
for(int i=0; i<Nmax; i++)
{
best[i] = 0;
}
best[0] = 1;
pre[0] = -1;
lastindex = 0;
}
void writeData(char* fileName)
{
ofstream outFile (fileName);
outFile << maxindex << '\n';
for(int i=maxindex-1; i>=0; i--)
{
outFile << sol[i] << " " ;
}
outFile.close();
}
void doSol()
{
int i = lastindex;
int k = 0;
while(i!= -1)
{
sol[k] = dataString[i];
i = pre[i];
k++;
}
}
void doDynamic()
{
maxindex =-1;
for(int i=1; i<n; i++)
{
best[i] = 1;
pre[i] = -1;
for(int j=0; j<i; j++)
{
if(dataString[i] > dataString[j] && best[i] <= best[j])
{
best[i] = best[j] +1;
pre[i] = j;
}
if(best[i] > maxindex)
{
maxindex = best[i];
lastindex = i;
}
}
}
}