uva 497 - Strategic Defense Initiative Solution

uva 497 - Strategic Defense Initiative Solution

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>

using namespace std;

vector<int> list,order;

int convertStringToInt(string str){
int i, len=str.length(), sum = 0,mul=1;
for (i = len - 1; i >= 0; i--){
sum = sum + (str[i] - 48)*mul;
mul = mul * 10;
}
return sum;
}

int getMaxTargets(){
int len = list.size(),i,j,max=1,last_index=0;
int *count = new int[len],*index=new int[len];
fill(count, count + len, 1);
fill(index, index + len, -1);
order.clear();
for (i = 1; i < len; i++){
for (j = 0; j < i; j++){
if (list[i] > list[j]){
if (count[j] + 1>count[i]){
count[i] = count[j] + 1;
if (max < count[i]){
max = count[i];
last_index = i;
}
index[i] = j;
}
}
}
}
order.push_back(last_index);
for (i = 1; i < max; i++){
last_index = index[last_index];
order.push_back(last_index);
}
return max;
}

int main(){
int x,test_case,i;
char ch;
string str;
bool flag = false;
cin >> test_case;
getchar();
getline(cin,str);
while (test_case--){
if (flag)
cout << endl;
flag = true;
list.clear();
while (true){
getline(cin, str);
if (str.length() == 0)
break;
list.push_back(convertStringToInt(str));
}
cout <<"Max hits: "<< getMaxTargets() << endl;
for (i = order.size() - 1; i >= 0; i--){
cout << list[order[i]] << endl;
}
}
return 0;
}