#include <stdio.h>
#include <stdlib.h>


void recursivePrinting(int* arr, int* sequenceIndexs, int index){
    int nextIndex = sequenceIndexs[index];

    printf("%d ", arr[index]);

    if (sequenceIndexs[nextIndex] == -1) {
        return;
    }
    recursivePrinting(arr,sequenceIndexs, nextIndex);

}

void printfLongestIncreasingSequence(int* arr, int* sequenceIndexs, int size){
    int currentIndex = size - 1;
    while (sequenceIndexs[currentIndex] == -1) {
        currentIndex--;
    }
    recursivePrinting(arr,sequenceIndexs, currentIndex);
}

int main(){
    int arr[] = {0,4,12,2,10,6,9,13,3,11,7,15};
    int size = sizeof(arr)/sizeof(int);
    int longestSubSequencesLenghts[size];
    int longestSubSequence[size];
    int i;
    for(i = 0; i < size; i++){
        longestSubSequencesLenghts[i] = 1;
        longestSubSequence[i] = -1;
    }

    int j;
    for (i = 1; i < size; i++) {
        for(j = 0; j < i; j++){
            if (arr[j] < arr[i]) {
                int currentLenght = longestSubSequencesLenghts[i];
                int newLenght = longestSubSequencesLenghts[j]+1;
                if (currentLenght > newLenght) {
                    longestSubSequencesLenghts[i] = currentLenght;
                } else {
                    longestSubSequencesLenghts[i] = newLenght;
                    longestSubSequence[i] = j;
                }

            }
        }
    }
    puts("");
    int x;
    for(x = 0; x < size; x++){
        printf("%d ", longestSubSequencesLenghts[x]);
    }

    puts("");
    for(i = 0; i < size; i++){
        printf("%d ", longestSubSequence[i]);
    }
    puts("************************************************");

    printfLongestIncreasingSequence(arr,longestSubSequence,size);
    return 0;
}