uva 481 - What Goes Up Solution

uva 481 - What Goes Up Solution

#include<iostream>
#include<vector>

using namespace std;

void binary_search(int *arr, int search_value, int start, int end, int &index){
if (start == end){
index = start;
return;
}
int mid = (start + end) / 2;
if (arr[mid] == search_value){
index = mid;
return;
}
else if (arr[mid + 1] == search_value){
index = mid + 1;
return;
}
else if (arr[mid]<search_value && arr[mid + 1]>search_value){
index = mid + 1;
return;
}
else if (arr[mid] > search_value){
binary_search(arr, search_value, start, mid, index);
}
else{
binary_search(arr, search_value, mid + 1, end, index);
}
}

void calculate_lis(vector<int>&arr,vector<int>&result){
int *temp, i, max = 0, j, index, n = arr.size(), *res;
temp = new int[n];
res = new int[n];
temp[0] = 0;
for (i = 1; i < n; i++){
if (arr[temp[max]] < arr[i]){
res[i] = temp[max];
max++;
temp[max] = i;
}
else if (arr[temp[max]] == arr[i] || arr[temp[0]] == arr[i]){

}
else if (arr[temp[0]] > arr[i]){
temp[0] = i;
}
else{
int *temp_arr = new int[max];
for (j = 1; j <= max; j++)
temp_arr[j - 1] = arr[temp[j]];
binary_search(temp_arr, arr[i], 0, max - 1, index);
index++;
if (arr[index] == arr[i]){

}
else{
res[i] = temp[index - 1];
temp[index] = i;
}
}
}
result.push_back(arr[temp[max]]);
index = temp[max];
for (i = max-1; i >=0; i--){
index = res[index];
result.push_back(arr[index]);
}
}


int main() {
vector<int> input, result;
int x, i;
while (cin >> x)
input.push_back(x);
calculate_lis(input, result);
cout << result.size() << endl << "-" << endl;
for (i = result.size() - 1; i >= 0; i--)
cout << result[i] << endl;
return 0;
}