Print longest increasing subsequence

#include <iostream>

#include <vector>

#include <map>

using namespace std;

// [10,9,2,5,3,7,101,18]

vector<int> LIS(vector<int>& input) {

    vector<int> output;

    if (input.size() == 0) {

        return output;

    }

    vector<pair<int, int>> dp(input.size());

    int itr = 0;

    for (auto& elem : dp) {

        elem.first = 1;

        elem.second = itr++;

        cout << "dp: set" << elem.first << ": " << elem.second << endl;

    }

    for (auto elem : dp) {

        cout << "dp: ge" << elem.first << ": " << elem.second << endl;

    }

    // length, index

    // 10,9,2,5,3,7,101,18

    

    dp[0] = make_pair(1, 0);

    for (int i = 1; i < input.size(); i++) {

        for (int j = i - 1; j >= 0; j--) {

            if (input[i] > input[j] && dp[i].first < dp[j].first + 1) {

                dp[i].first = dp[j].first + 1;

                dp[i].second = j;

            }

        }

    }

    

    // generate:

    int max_elem = 0, max_iter = -1;

    for (int i = 0; i < dp.size(); i++) {

        auto elem = dp[i];

        if (elem.first > max_elem) {

            max_elem = elem.first;

            max_iter = i;

        }

    }

    

    // 10,9,2,5,3,7,101,18

    int iter = max_iter;

    while (iter >= 0) {

        int element = input[iter];

        output.push_back(element);

        int index = dp[iter].second;

        if (index == iter) {

            break;

        }

        iter = index;

        if (iter == 0) {

            break;

        }

    }

    

    for (auto elem : dp) {

        cout << "dp: " << elem.first << ": " << elem.second << endl;

    }

    return output;

}

int main()

{

    cout<<"Hello World" << endl;

    vector<int> input = {10,9,2,5,3,7,101,18};

    vector<int> output = LIS(input);

    for (auto elem : output)

    cout << elem << endl;

  

    return 0;

}