i got the code for this problem but not able to find where i am wrong
my problem is as follows

Given an array of numbers, find the longest subsequence whose elements grow monotonically:
1 4 8 2 5 7 3 6 => 1 4 5 7
1 4 8 2 5 7 3 6 7 => 1 4 5 6 7
1 4 8 2 3 7 4 6 => 1 2 3 4 6
that is we must form subsets and find which is longest among them
as showed in the above example

#include<iostream.h>
#include<conio.h>

int maxRank (int curr, int* arr, int* rank) {
    int max = 0 ;
    for (int i = 0; i <= curr; i++) {
        if (arr[i]<arr[curr] && rank[i]>rank[max]) {
            max = i ;
        }
    }

    return max ;
}

void printReverse (int curr, int* arr, int* back) {
    if (curr == 0) return ;
    printReverse (back[curr], arr, back) ;
    cout << arr[curr] << " " ;
}

void longestMonotoneSubsequence (int count, int* arr) {
    int* back = new int[count] ;
    int* rank = new int[count] ;
    int max = 0 ;
    rank[0] = 0, back[0] = 0 ;
    for (int i = 0; i <= count; i++) {
        back[i] = maxRank (i, arr, rank) ;
        rank[i] = rank[back[i]]+1 ;
        if (rank[i] > rank[max]) {
            max = i ;
        }
    }

    printReverse (max, arr, back) ;
    cout << "\n" ;
    delete rank, back ;
}

void main()
{
int n;
int a[100];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
longestMonotoneSubsequence(n,&a);
}

Edited 3 Years Ago by Reverend Jim: Fixed formatting

This article has been dead for over six months. Start a new discussion instead.