#include<stdio.h>
#include<assert.h>

#define MAX_N 100

int maxlength=0;

int n = 18; 
int s[]={7,4,6,1,3,4,6,5,4,6,5,2,8,9,3,2,7,6};
//int s[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
//int s[]={18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
//int s[]={1,2,4,8,16,32,5,6,7,9,10,11,12,13,14,15,16,17};
//int s[]={8,16,32,5,6,7,9,10,11,12,13,14,15,16,1,2,4,17};


void print(int* v, int n){
	int i=0;
	for(i=0; i<n; i++){
		printf("%d ", v[i]);
	}
	printf("\n");
}

void increasingSub(int i, int j, int* subs, int length){
// <subs> contiene una sottosequenza crescente di s la cui lunghezza e' <length>.
// <i> e' l'indice in s dell'ultimo elemento preso dalla sottosequenza <subs>.
// <j> e' un indice in s successivo a <i>.
// stampo tutte le sottosequenze crescenti di s aventi <subs> come prefisso e che come ulteriori
//  elementi peschino da s successivamente a <j>.
 
	// prints an increasing substring if it is longer than all pervious
	// (the last one will be the longer)
	assert(i<j);
	assert(length<=n);

	if(j>=n){
		if(length>maxlength) {
			maxlength=length;
			print(subs, length);
			}
		return;
	}
 
	if(s[i]<s[j]){
	// store the integer as part of the increasing substring
		subs[length]=s[j];
		increasingSub(j, j+1, subs, length+1);

	// discard this increasing int, looking for
	// possible other substring longer forward
		increasingSub(i, j+1, subs, length);
	}
	else{
		// keep reading the string forward
		increasingSub(i, j+1, subs, length);

		// store the integer as a new substrings of s[i]...s[j] 
		int subs2[MAX_N];
		subs2[0]=s[j];
		increasingSub(j, j+1, subs2, 1);
	}
}

int main(){
	int sub[MAX_N];
	sub[0]=s[0];
	increasingSub(s, 0, 1, sub, 1);
}