CareerCup

Just a little modification to the dynamic approach..I used a LISindex array to keep track of the element that comes before the current element.If any doubts ,Give a reply

#include<stdio.h>
#include<stdlib.h>
 
int lis( int arr[], int n )
{
   int *lisindex=(int *)malloc(sizeof(int) * n);
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );
   int lastLISindex;
   int check,k=0;
   
   for ( i = 0; i < n; i++ )
      lis[i] = 1;
    
   for ( i = 1; i < n; i++ )    {
      for ( j = 0; j < i; j++ ) {
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)   {
            lis[i] = lis[j] + 1;
            lisindex[i]=j;
      }
   }
   }
   /* Pick maximum of all LIS values */
   for ( i = 0; i < n; i++ )    {
      if ( max < lis[i] )
         max = lis[i];
         lastLISindex=i;
   }
   
   int *arrSeq=(int *)malloc(sizeof(int) * max);
   
   for(int index=max-1;index>=0;index--) {
       arrSeq[index]=arr[lastLISindex];
       lastLISindex=lisindex[lastLISindex];
   }
   
   for(int index=0;index<max;index++)   {
       printf("%d ",arrSeq[index]);
   }
   
   /* Free memory to avoid memory leak */
   free( lis );
 
   return max;
}
 
/* Driver program to test above function */
int main()
{
  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  int n = sizeof(arr)/sizeof(arr[0]);
  lis( arr, n ); 
 
  getchar();
  return 0;
}

There is another way to find LIS, similar to patient sort, where you keep piles (stacks) to keep the increasing sequences. Here is the link and explanation of the algorithm: wordaligned.org/articles/patience-sort.

By using this method, you can not only print the longest increasing sequence, but also print all the longest subsequences, if there are more than one maximum subsequence.

@Nascent, is it consecutive numbers or just order in the given sequence should be considered ?

int longstr(int val[],int size)
{
    int arr[size];
    int i=0,j=1,count1=1,max=0,temp,index;
    for( i = 0 ; i < size ; i++)
    {
        if(val[i] < val[j])
        {
            //printf(" in if The array is:%d ",val[j]);
            j++;
            count1++;  
        }
        if(max < count1)
        {
            max = count1;
            temp = j-(max);
            index = 0;
            while( temp <= j)
            {
                arr[index] = val[temp];
                temp ++;
                //printf("The array is: %d",arr[index]);
                index++;
            }
        }
            
        if(val[i] >= val[j-1])
        {
           // printf("in else The array is:%d ",val[j]);
            count1 = 1;
            j++;
        }
        
    }
    for( index = 0; index < max; index++)
        printf("%d ",arr[index]);
    printf("The max number is:%d",max);
    return max;
}
int main()
{
    int val = 0;
    int arr[]={1,5,7,8,9,45,78,2,4,1,7,12,23,34,6,23,45};
    int size = sizeof(arr)/sizeof(arr[0]);
    val=longstr(arr,size-1);
    return 1;
}

The following code prints a longest "strictly" increasing subsequence.
For example for {7, 7, 7, 7} it prints {7}. Only a little modification is required to print a longest non-decreasing subsequence.

Dynamic Programming. Time complexity O(n^2).

//lisLen[i] stores the length of longest increasing subsequence starting at index i.
//next[i] stores the index of next element in the longest increasing
//subsequence starting at index i.
int lisLen[SIZ], next[SIZ];

void printLIS(int a[], int len){
	int i, j, max, index;

	lisLen[len-1] = 1;	
	next[len-1] = -1;	//-1 indicates that there is no next number after this one.

	for(i=len-2 ; i>=0 ; i--){
		lisLen[i] = 1;
		next[i] = -1;
		for(j=i+1 ; j<=len-1 ; j++){
			if(1+lisLen[j] > lisLen[i] && a[i]<a[j]){
				lisLen[i] = 1 + lisLen[j];
				next[i] = j;
			}
		}
	}

	max = 0;
	for(i=0 ; i<len ; i++){
		if(lisLen[i] > max){
			max = lisLen[i];
			index = i;
		}
	}
	while(next[index] != -1){
		cout<<a[index]<<" ";
		index = next[index];
	}
	cout<<a[index]<<"\n\n";
}

Use dynamic programming approach.

Maintain a 2D array.
ith row will store the longest increasing sequence for ith number in the original array.
For optimization purpose, you can use another array to maintain the length of each row. Call it lengthArray.

Use DP approach to find longest increasing sequence for all the numbers from 0 to nth elements. Each time update the lengthArray.

at the end, iterate through lengthArray and find the largest element.
Lets say its jth.

Now print jth row from 2D array.

i defined a separate datastructure such that it keeps track of the indexex forming the LIS

#include<iostream>
using namespace std;
struct lis
{
	int count;
	int index;
};

void display(int a[],lis t[],int n,int pos)
{
	if(t[pos].index!=pos)
	{
		display(a,t,n,t[pos].index);
	}
	cout<<a[pos]<<"  ";
	return;
}

int lisnum(int a[],int n)
{
	lis t[n];
	for(int i=0;i<n;i++)
	{
		t[i].count=1;
		t[i].index=i;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(a[i]>a[j]&&1+t[j].count>t[i].count)
			{
				t[i].count=1+t[j].count;
				t[i].index=j;
			}
		}
	}
	int max=-10,pos=-1;
	for(int i=0;i<n;i++)
	{
		if(t[i].count>max)
		{
			max=t[i].count;
			pos=i;
		}
	}
	display(a,t,n,pos);
	return max;
}

int main()
{
	cout<<"enter the program. \n";
	int n,*a;
	cout<<"Enter the size. \n";
	cin>>n;
	a=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int t=lisnum(a,n);
	cout<<"Length="<<t;
	return 0;
}

i hope this could serve the purpose...
tell me if any doubts... regarding the program..

i defined a separate datastructure such that it keeps track of the indexex forming the LIS

#include<iostream>
using namespace std;
struct lis
{
	int count;
	int index;
};

void display(int a[],lis t[],int n,int pos)
{
	if(t[pos].index!=pos)
	{
		display(a,t,n,t[pos].index);
	}
	cout<<a[pos]<<"  ";
	return;
}

int lisnum(int a[],int n)
{
	lis t[n];
	for(int i=0;i<n;i++)
	{
		t[i].count=1;
		t[i].index=i;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(a[i]>a[j]&&1+t[j].count>t[i].count)
			{
				t[i].count=1+t[j].count;
				t[i].index=j;
			}
		}
	}
	int max=-10,pos=-1;
	for(int i=0;i<n;i++)
	{
		if(t[i].count>max)
		{
			max=t[i].count;
			pos=i;
		}
	}
	display(a,t,n,pos);
	return max;
}

int main()
{
	cout<<"enter the program. \n";
	int n,*a;
	cout<<"Enter the size. \n";
	cin>>n;
	a=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int t=lisnum(a,n);
	cout<<"Length="<<t;
	return 0;
}

i hope this could serve the purpose...
tell me if any doubts... regarding the program..

Can we use LCS here?

This was a great (and tricky) question. I challenged myself to implement a single pointer traversal, instead of using a leading/trailing pointer. The running time of this algorithm should be O(n) as it simply scans each element and copies to the new array. In the worst case it would scan and copy each element once if this was a sorted (ascending) array of integers.

This problem also required that I make special consideration for the last element in the array, should it be part of the largest ascending sequence, thus the use of the ternary operators evaluating on i==a.length.

Assumption: Duplicates are not considered "increasing", so they are not counted as such and cause the 'count' to start over.

I also incorporated Java's ArrayList class so that I could account for increasing sequences that have the same length, and subsequently print all of them.

I hope this proves helpful =)

NOTE: I use a file with 100,000 randomly generated integers to test, that is the reason for the scanner at the start to load my test case.

Scanner scanner = new Scanner(new File("IntegerArray.txt"));
        int [] a = new int [100000];
        int k = 0;
        while(scanner.hasNextInt()){
           a[k++] = scanner.nextInt();
        }
        
        ArrayList<int[]> resultSet = new ArrayList<>();
        int[] result = new int[1];
        int i, j;
        int count = 1;  //first element in sequence always counted
        
        for(i=1; i < a.length; i++){
            if(a[i-1] < a[i]){
                count++;  //increase the current count when increasing element found
            }
            else
            if(count >= result.length && (a[i-1] >= a[i] || i == a.length -1) ){
                if(count > result.length){resultSet.clear();}
                result = new int[count];
                for(j = 0; j < result.length; j++){
                    result[j] = (i == a.length-1) ?  a[i-count+j+1] : a[i - count + j];
                    //edge case (End) - to make sure we capture the last element
                    //if it is part of the largest increasing sequence
                }
                count = 1;
                resultSet.add(result);
            }
            else{count = 1;}
        }
        
        for(i=0; i < resultSet.size(); i++){
            int[] temp = resultSet.get(i);
            for(int x = 0; x < temp.length; x++){
                System.out.println(temp[x] + " ");
            }
            System.out.println();
        }

Just to understand the question,
if the input is {1,5,7,8,9,45,78,2,4,1,7,12,23,34,6,23,45};
The increasing sub-arrays are
{1,5,7,8,9,45,78} -> Longest and should be the result.
{2,4}
{1,7,12,23,34}
{6,23,45}

The output should be {1, 5, 7, 8, 9, 45, 78}

Can someone confirm?

#include <iostream>
#include <vector>
using namespace std;

int main()
{
std::vector<int>vec;
int arr[7]={1,9,2,4,7,2,3};
int matrix[7][8];

for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
matrix[i][j]=99;

matrix[0][1]=arr[0];

for(int i=1;i<7;i++)
for(int j=1;j<8;j++)
{
if(arr[i]>matrix[i-1][j-1]&&arr[i]<matrix[i-1][j])
matrix[i][j]=arr[i];
else
matrix[i][j]=matrix[i-1][j];
}

int k=6;
int j;
for(j=1;j<8;j++)
{
if(matrix[k][j]==99)
{
break;
}
}
j--;
while(matrix[k][j]!=99)
{
cout<<matrix[k][j];
vec.push_back(matrix[k][j]);
k--;
j--;
}

int m=vec.size();
for (int i=m;i>0;i--)
{
cout<<vec[i];
}
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    std::vector<int>vec;
int arr[7]={1,9,2,4,7,2,3};
int matrix[7][8];

for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
matrix[i][j]=99;

matrix[0][1]=arr[0];

for(int i=1;i<7;i++)
for(int j=1;j<8;j++)
{
    if(arr[i]>matrix[i-1][j-1]&&arr[i]<matrix[i-1][j])
      matrix[i][j]=arr[i];
    else
      matrix[i][j]=matrix[i-1][j];
}

int k=6;
int j;
for(j=1;j<8;j++)
{
    if(matrix[k][j]==99)
    {
        break;
    }
}
j--;
while(matrix[k][j]!=99)
{
    cout<<matrix[k][j];
    vec.push_back(matrix[k][j]);
    k--;
    j--;
}

int m=vec.size();
for (int i=m;i>0;i--)
{
    cout<<vec[i];
}
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    std::vector<int>vec;
int arr[7]={1,9,2,4,7,2,3};
int matrix[7][8];

for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
matrix[i][j]=99;

matrix[0][1]=arr[0];

for(int i=1;i<7;i++)
for(int j=1;j<8;j++)
{
    if(arr[i]>matrix[i-1][j-1]&&arr[i]<matrix[i-1][j])
      matrix[i][j]=arr[i];
    else
      matrix[i][j]=matrix[i-1][j];
}

int k=6;
int j;
for(j=1;j<8;j++)
{
    if(matrix[k][j]==99)
    {
        break;
    }
}
j--;
while(matrix[k][j]!=99)
{
    vec.push_back(matrix[k][j]);
    k--;
    j--;
}

int m=vec.size();
for (int i=m-1;i>=0;i--)
{
    cout<<vec[i];
}
return 0;
}

Here all the solutions are O(n^2); nlogn solution is given on algoritihmist site using binary search.

what about radix sort approach:
1.given *a, create b[],c[],d[] = {0} string/int arrays and exp =1 , m= a[0], int count =0; and other declarations
2. while (m/exp>0) 
        for (i=0:n-1)
		b[i] = a[i]/exp %10;
	for(i=0:n-1)
		count++;
		a[i] = b[i];
		
		if(count != 1)
			for(i=0:n-1)
				c[i]>b[i]
				d[i]++
			
		c[i] = b[i]

3. then d[i] will have the maximum increasing sequence for each entry. 
4. then check the longest from the d array and return it.

Traverse Array and keep track of current AscSequenceStartIndex, AscSequenceLength and AscSequenceEndIndex.
At the end print elements from index AscSequenceStartIndex to AscSequenceEndIndex