CareerCup

Well, this is a simple problem which can be solved iteratively, but not sure why it was asked for recursion. As they want, here is my attampt in java:

public class PrintSubsequences {
    public void printSubsequence(int[] array, int index, int biggestNumber){
        if(index < array.length){
            if(array[index] >= biggestNumber){
                System.out.print(array[index]);
                printSubsequence(array,index+1, array[index]);
            }else
                printSubsequence(array, index+1, biggestNumber);
        }
        
    }

    public void printAllSequences(int[] array, int index){
        if(index < array.length){
            printSubsequence(array, index, array[index]);
            System.out.println("\none more sequence completed ");
            System.out.println("\n one more sequence completed ");
            printAllSequences(array, index+1);
        }
    }
    
    public static void main(String[] args){
        int[] array = new int[]{5,4,7,8,2,3,6,9,8,6,2,3,4,5};
        PrintSubsequences printSubsequences = new PrintSubsequences();
        printSubsequences.printAllSequences(array,0);
    }

}

import java.util.ArrayList;
import java.util.List;

class SubSeqByRecursion{
void longestSubSeq(String rest,List list){
for(int i=0;i<rest.length();i++){
helperSubSeq("", rest.substring(i), list);
}
}
private void helperSubSeq(String soFar,String rest,List list){
if(rest.length() == 0){
//System.out.println(soFar);
list.add(soFar);
}
else{
if(soFar == ""){
soFar = soFar + rest.charAt(0);
//System.out.println(soFar);
}
else if(soFar.charAt(soFar.length()-1) < rest.charAt(0)){
soFar = soFar + rest.charAt(0);
//helperSubSeq(soFar, rest.substring(1), list);
}
helperSubSeq(soFar, rest.substring(1), list);
}
}
}
public class SubSeq {
public static void main(String[] args) {

SubSeqByRecursion subseq = new SubSeqByRecursion();
List list = new ArrayList();
subseq.longestSubSeq("54782369862345", list);
System.out.println("List with all increasing sub seqs:" + list);
int maxLength=0;
for (int i=0;i<list.size();i++){
String temp = (String)list.get(i);
if(temp.length()>maxLength){
maxLength = temp.length();
}
}
System.out.println("Max Increasing sub seq strings");
for (int i=0;i<list.size();i++){
String temp = (String)list.get(i);
if(temp.length() == maxLength){
System.out.println(temp);
}
}
}

}

This could be written in a better way but this is what came in first to my mind :P

Here is my another attempt with String:

public class PrintSubsequences { 
    public static void printStringSubsequnces(String str, int index, char biggestNumber){
        if(index < str.length()){
            if(str.charAt(index) >= biggestNumber){
                System.out.print(str.charAt(index));
                printStringSubsequnces(str, index+1, str.charAt(index));
            }else
                printStringSubsequnces(str, index+1, biggestNumber);
        }
    }
    
    public static void printStringSequenceHelper(String str, int index){
        if(index < str.length()){
            printStringSubsequnces(str, index, str.charAt(index));
            System.out.print("\n");
            printStringSequenceHelper(str, index+1);
        }
    }
    
    public static void main(String[] args){
        PrintSubsequences.printStringSequenceHelper("54782369862345", 0);
    }
}

#include<stdio.h>
#define INFINITY 999

int arr[10]={5,12,3,-6,4,7,19,13,10,17};
int flag[10];

void print_increasing_seq(int arr_index, int curr_max, int size)
{
    int i;

    if(arr_index==size)
    {
        printf("\n");
        for(i=0;i<size;i++)
        {
            if(flag[i])
            {
                printf("%3d",arr[i]);
            }
        }
    }
    else
    {
        if(arr[arr_index]>curr_max)
        {
            flag[arr_index]=1;
            print_increasing_seq(arr_index+1, arr[arr_index], size);
            flag[arr_index]=0;
            print_increasing_seq(arr_index+1, curr_max, size);

        }
        else
        {
            print_increasing_seq(arr_index+1, curr_max, size);

        }
    }
}


int main()
{
    print_increasing_seq(0, -INFINITY, 10);
    return 0;
}

#include<stdio.h>
#define MAX 1000
void print_nck( int from[],int idx,int n,int val)
{  
    int i;
    if(idx ==n)
    return;
	for(i=idx;i<n;i++)
	{
      if(val <= from[i])
      {
         printf("%d ",from[i]);
         val=from[i];
      }
      
     
   }
   printf("\n");
    print_nck(from,idx+1,n,from[idx+1]); 
         
}
int main()
{
	int from[] = {6,5,3,1,2,10,9,8,13,15};
	int comb[MAX];
//	comb[0]=from[0];
  	print_nck(from,0,10,from[0]);
  	getchar();
  	getchar();
	return 0;
}

/*
Print all the increasing subsequence from the given range 54782369862345 .. ex: 5,7,8,9; 4,7,8,9; 2,3,6,9 ..
using Recursion
*/

#include <stdio.h>

void print(char prev, char *c)
{
while (*c && *c < prev)
c++;

if (!*c) {
printf("; ");
return;
}

if (prev >= '0')
printf(", ");

printf("%c", *c);
print(*c, c + 1);
}

int main(int argc, char *argv[])
{
char data[] = "54782369862345";
char *ptr = &data[0];

while (*ptr) {
print((char)0, ptr);
ptr++;
}

return 0;
}

void display(int arr[], int n, int index, vi result) {
	if (index == n) {
		for(int i=0, i <= (int)result.size()-1, ++i)
			printf("%d ",result[i]);
		printf("\n");
		return;
	}
	display(arr,n,index+1,result);
	if(!result.size() || arr[index] > result.back()) {
		result.push_back(arr[index]);
		display(arr,n,index+1,result);
	}
}

int main() {
	int arr[] = {5,4,7,8,2,3,6,9,8,6,2,3,4,5};
	vector<int> t;
	display(arr,sizeof(arr)/sizeof(arr[0])-1,0,t);
	return 0;
}

use dynamic programing to solve this problem