CareerCup

Backtracking would not be doable for moderate size of n even (like 100).

DP can solve it in O(n^2 k) time. The idea is: for each i-th element (0<=i<=n-1) and j-th index (0<=j<=k-1), count[i][j] stores the number of ways a subsequence of length j+1 can be constructed considering elements [0,i-1]. Initialize count[i][0] = 1 for all i.

The recurrence is like:
count[i][j] = sum { count[a][b] such that value[a] < value[i], for 0<=a<=i-1,  
0<=b<=j-1}

For input, 1 4 6 2 5 9 and k = 3
output: 10
1 4 6
1 4 5
1 2 5
2 5 9
4 5 9
1 5 9
1 2 9
4 6 9
1 6 9
1 4 9

backtracking would do..
p.s: i think 1,2,6 is not a valid subsequence for the above example

start with subsequence(A,n,k,v,0);


void subsequence(int A[],int n, int k, vector<int> v, int idx)
{
    if(v.size() == k)
    {
        for(int i=0;i<v.size();i++) cout << " " << v[i];
        cout << endl;

        return;
    }
    
    for(int i=idx;i<n;i++)
    {
       if(v.size() == 0 || A[i] > v[v.size()-1])
       {
           v.push_back(A[i]);
           subsequence(A,n,k,v,i+1);
           v.pop_back();
       }
    }
}

Solution in Python using DP O(n^2 k) solution.

#!/usr/bin/env python

A = [1,4,6,2,5,9]
n = len(A) 
k = 3
T = [[0 for j in range(n)] for i in range(k)]

for x in range(n):
    T[0][x] = 1

for i in range(1,k):
    for j in range(n):
        curr = A[j]
        count = 0
        for x in range(j):
            if A[x] < A[j]:
                count += T[i-1][x]
        T[i][j] = count
        
count = sum(T[k-1])
print 'Total no. of ways:',count

subsequences if the array is sorted??
if so, why not 2 4 5, 2 4 6....etc..??
if no, then why is 1 2 6 an answer?

a Java alternative which take less parameter (because it is Java :).) Simply call subsequence3("146259"); in your main function. It will output as @buried.shopno stated earlier.

/**
	 * Print all increased subsequence size 3 given 
	 * an unsorted array of integer.
	 * @param nums
	 */
	public static void subsequence3(String nums){
		StringBuffer bf_ = new StringBuffer();
		for(int i=0;i<nums.length()-1;i++){
			bf_.append(nums.charAt(i));
			subsequence3(nums,bf_,i+1);
			bf_.setLength(0);
		}
	}
	
	private static void subsequence3(String nums, StringBuffer bf_, int bgn){
		//base case 1
		if (bf_.length() == 3){
			System.out.print(bf_.toString()+ " ");
			return;
		}
		//base case 2
		if (bgn >= nums.length())
			return;
		//recursive case
		char c = bf_.charAt(bf_.length()-1);
		for(int i=bgn;i<nums.length();i++)
		{
			//Check if nums[i] is greater thaan last digit 
			if(nums.charAt(i) > c){
				bf_.append(nums.charAt(i));    // add nums[i]
				subsequence3(nums,bf_,i+1);
				bf_.setLength(bf_.length()-1); // remove nums[i]
			}
		}
	}

#include <stdio.h>

/* Prints all the subarrays of length r */

/* @params: a, given array */
/* @params: n, a length */
/* @params: sub, sub array */
/* @params: r, sub length */
/* @params: i, current index of a */
/* @params: j, current index of sub */

void subarray(int a[], int n, int sub[], int r, int i, int j)
{
if(j == r) /* current index of sub r, print sub */
{
int k;

printf("( ");

for(k = 0; k < r; k++)
printf("%d ", sub[k]);

printf(")\n");
}
else
{
if(i < n)
{
sub[j] = a[i];

subarray(a, n, sub, r, i + 1, j + 1); /* Include current element */
subarray(a, n, sub, r, i + 1, j); /* Override the current element */
}
}

}

int main()
{
int n=10, r=3;



int a[10]={1,2,3,4,5,6,7,8,9,10}, sub[3];

int i;

subarray(a, n , sub, r, 0, 0);
}

The problem can be solved in O(nlogn*K) check the problem INCSEQ on spoj using AVL trees or segment trees or Fenwick trees

The question says - find the number of ways in which you can select the sequences of length k. I think the answer is [nCk] .

//n- size of the main array
//k - size of subsequence

int i,j,k=3,a[6]={1,4,9,7,10,6},c[3]={0,0,0};
int m=0;
int n=6,p;
for (i=0;i<(n-k);i++)
{
c[m]=a[i];
for (j=i+1;j<n;j++)
{
if (a[j] > c[m] && m!=(k-1))
{
c[++m]=a[j];
if ( m == (k-1))
{
for (p=0;p<k;p++)
printf("%d ",c[p]);
printf("\n");
m--;
}
}
}
m=0;
}

1. Sort it, and print it in groups of k elements
2. Make a HashMap where, heightes number of the set is key and linked-list of set is the value... Keep inserting, in appropriate posiotns

This solution uses a Hashtable, where hash[n] stores the number of consecutive from elements {x,...,n}. For simplicity we'll assume no duplicates.

1) Create cache variables maxCounts and startIndexOfMax

2) For a number n:

hash[n] = hash[n-1] > 0 ? hash[n-1]+1 : 0; 
   int i = 1;
   while(hash[n+i] != null)
   {
      hash[n+i] = hash[n+i-1] + 1;
      i++;
   }

3) Of course update maxCounts and startOfMax if necessary.

Worst case performance is if values are in reverse order (5,4,3,2,1). In which case shuffle or start reading from the tails.

R