CareerCup

geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/

subsequence doesn't necessarily mean consecutive numbers, right?

A simple way of finding the longest increasing subsequence is to use the Longest Common Subsequence (Dynamic Programming) algorithm.
1. Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
2. Use Longest Common Subsequence on with A and B. O(n2) time.

Credit goes to

www  .  algorithmist  .  com   /  index  . php /     Longest_Increasing_Subsequence

None of the solutions on this page appear to work for the case where the sequence is not contiguous. Here are 2 solutions to that problem. First a brute force 2^n solution that loops through the set of all subsequences.

static int[] naiveMaximumSortedSubsequence(int arr[]) {
		ArrayList<Integer> maxSubsequence = new ArrayList<Integer>();
		ArrayList<Integer> subsequence = new ArrayList<Integer>();
		naiveMaximumSortedSubsequence2(maxSubsequence, subsequence, arr, 0);
		int result[] = new int[maxSubsequence.size()];
		for (int i = 0; i < maxSubsequence.size(); ++i) {
			result[i] = maxSubsequence.get(i);
		}
		return result;
	}
	
	static void naiveMaximumSortedSubsequence2(ArrayList<Integer> maxSubsequence, ArrayList<Integer> subsequence, int arr[], int i) {
		if (i == arr.length) {
			if (isSorted(subsequence) && subsequence.size() > maxSubsequence.size()) {
				maxSubsequence.clear();
				for (int v : subsequence) {
					maxSubsequence.add(v);
				}
			}
			return;
		}
		else {
			subsequence.add(arr[i]);
			naiveMaximumSortedSubsequence2(maxSubsequence, subsequence, arr, i+1);
			subsequence.remove(subsequence.size() - 1);
			naiveMaximumSortedSubsequence2(maxSubsequence, subsequence, arr, i+1);
		}
	}
	
	static boolean isSorted(ArrayList<Integer> arr) {
		for (int i = 1; i < arr.size(); ++i) {
			if (arr.get(i) < arr.get(i-1)) {
				return false;
			}
		}
		return true;
	}

Next a n^2 solution that works as follows.

Create a list L of candidate subsequences.
For each number X in sequence
Find candidate subsequence C of maximum length that X can be appended to
Create new candidate subsequence that is a copy of C
Append X to C
Add C to L

static class Candidate {
		public int value;
		public int size;
		public Candidate previous;
		@Override
		public String toString() { return String.valueOf(value) + "," + size; }
	}
	
	// Still O(n^2)
	static int[] maximumSortedSubsequence(int arr[]) {
		int iterationCount = 0;
		LinkedList<Candidate> candidates = new LinkedList<Candidate>();
		for (int v : arr) {
			int maxLength = 0;
			Candidate candidateWithMaxLength = null;
			for (Candidate candidate : candidates) {
				if (candidate.value <= v) {
					if (candidate.size > maxLength) {
						maxLength = candidate.size;
						candidateWithMaxLength = candidate;
					}
				}
				++iterationCount;
			}
			Candidate newCandidate = new Candidate();
			newCandidate.previous = candidateWithMaxLength;
			newCandidate.value = v;
			newCandidate.size = 1 + (candidateWithMaxLength != null ? candidateWithMaxLength.size : 0);
			candidates.add(newCandidate);
			
			System.out.print("// " + v + ": ");
			for (Candidate candidate : candidates) {
				while (candidate != null) {
					System.out.print(candidate.value + ",");
					candidate = candidate.previous;
				}
				System.out.print("; ");
			}
			System.out.print(" iterations=" + iterationCount + "\n");
		}
		
		// Find candidate with the max length.
		int maxLength = 0;
		Candidate candidateWithMaxLength = null;
		for (Candidate candidate : candidates) {
			if (candidate.size > maxLength) {
				maxLength = candidate.size;
				candidateWithMaxLength = candidate;
			}			
		}
		
		// Convert ArrayList to int[]
		int result[] = new int[candidateWithMaxLength.size];
		for (int i = result.length - 1; i >= 0; --i) {
			result[i] = candidateWithMaxLength.value;
			candidateWithMaxLength = candidateWithMaxLength.previous;
		}
		return result;
	}

My solution might be similar to some others since this is a standard DP problem. Basically have 2 arrays:
(1) max[i] stores the maximum number of elements in the longest subsequence ending with arr[i]
(2) prev[i] stores the index of the previous element in the longest subsequence ending with arr[i]

So basically we just need to iterate through the array, update the 2 arrays above, and then keep traversing the "prev" array until we can't anymore.

static LinkedList<Integer> longest(int[] arr) {
	int len = arr.length;
	int max[] = new int[len];
	int prev[] = new int[len];
	for(int i=0; i<len; i++) {
		max[i] = 1;
		prev[i] = i;
		for(int j=0; j<i; j++) {
			if(arr[j] < arr[i] && max[j] + 1 > max[i]) {
				max[i] = max[j] + 1;
				prev[i] = j;
			}
		}
	}

	LinkedList<Integer> sequence = new LinkedList<Integer>();
	int index = len-1;
	while(true) {
		sequence.add(0, arr[index]);
		if(prev[index] == index)
			break;
		index = prev[index];
	}
	return sequence;
}

List<int> longestSequence(List<int> list){
  if(list == null  || list.size()==0) return null;

  List<int> longest = new LinkedList<>();
  List<int> current = new LinkedList<>();
  int previous = 0;
  for(int elem: list){
        if( current.size() == 0 || elem >= current.getLast()){
           current.add(elem);
       }
       else{
                 if(current.size() > longest.size() ){
                    longest = current; 
                 }
                    current = new LinkedList<>();   
                    current.add(elem);             
        }
   }
    if(current.size() > longest.size() ){
                    longest = current; 
    }
   return longest;
}

O(n)

void subsequence(const int *list, int size) {
	
	if (size == 0 || size == 1)
		return;
	int *M = new int[size];
        int *Post = new int[size];
        for (int i=0; i<size; i++) {
	       M[i] = 1;
	       Post[i] = -1;
         }
	M[size-1] = 1;
        Post[size-1] = -1;
        int front = 0;
        int longest = 0;
        for (int i=size-2; i>=0; i--) {
		int max = 0;
                for (int j=i+1; j<size; j++) {
			if (list[j] >= list[i] && max < M[j]+1) {
				max = M[j]+1;
				Post[i] = j;
				if (longest < max) {
					longest = max;
					front = i;
                               }
                      }
               }
          }

          while(front != -1) {
	         cout <<list[front]<<endl;
	         front = Post[front];
           }
           delete M;
           delete F;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int i,t,n,a,mx,lb;
	vector<int> v,res;
	cin>>t;
	while(t--)
	{
		cin>>n;
		v.clear();
		res.clear();
		while(n--)
		{
			cin>>a;
			v.push_back(a);
		}
		n=v.size();
		res.push_back(v[0]);
		mx=v[0];
		for(i=1;i<n;i++)
		{
			if(v[i]>mx)
				res.push_back(v[i]);
			else if(v[i]<mx)    
			{
				lb=lower_bound(res.begin(),res.end(),v[i])-res.begin();
				res[lb]=v[i];
			}
			mx=res[res.length()-1];
		}
		cout<<"The Longest Increasing Sequence is :\n";
		for(i=0;i<res.size();i++)
			cout<<res[i]<<' ';
		cout<<"\nLength of the LIS found = "<<res.size();
	}
}

/// @param a the array containing the numbers we are checking
    /// @param indices[out] The indices(inclusive) the function will return
    /// @return true if the finding is successful, false otherwise
    bool find(const vector<int>& a, pair<int, int>& indies)
    {
        if (a.empty()) return false;

        indies.first = 0;
        indies.second = 0;
        for (int i = 0, j = 0; j < a.size(); ++j)
        {
            if (a[j] > a[j - 1])
            {
                if (j - i > indies.second - indies.first)
                {
                    indies.first = i;
                    indies.second = j;
                }
            }
            else
            {
                i = j;
            }
        }
        return true;
    }

fill all a[i][j] for j = i +1

a[i][j] = a[i][k] && a[k][j] for k -> i+i..j-1

travers matrix a from [0][n], searching for max(j-i)
from the right, upper corner - go left
from the right, upper corner - go down

if all false, go to next right-upper corner

public static void findLongest(int[] array_) {
    int start = 0;
    int startIndex = 0;
    int endIndex = 0;
    for (int i = 0; i < array_.length-1; i++) {
      if (array_[i] > array_[i+1]) {        
        if (i - start > endIndex - startIndex) {        
          startIndex = start;
          endIndex = i;
        }
        start = i+1;
      }
    }
    
    System.out.println("array range is " + array_[startIndex] + " to " + array_[endIndex]);
  }

Python Solution for Subsequence (non-contiguous)

Many of the solutions on this page are solving the trivial problem of contiguous runs in a list. A subsequence can actually have gaps, which makes this a bit more challenging, but you can do it NlogN time. My solution is actually N-squared, but the linear search can be fairly trivially converted to a binary search.

# This solves the LSS problem--longest sorted subsequence.
def test():
    a = [7,8,1,5,4,6,9]
    assert LSS(a) == [1,4,6,9]

def LSS(a):
    if len(a) == 0:
        return []

    # candidate_maxes is an array of
    # the max value of a sorted subsequence
    # of length n, where n is the index
    # of the current element
    candidate_maxes = [a[0]]
    predecessor = {}
    for elem in a[1:]:
        if elem > candidate_maxes[-1]:
            # This is the case where our new element
            # extends the longest subsequence so far.
            predecessor[elem] = candidate_maxes[-1]
            candidate_maxes.append(elem)
        else:
            # Do a linear search to see if we
            # can make one of our previous subsequences
            # easier to extend. For a large N, we could
            # convert this to a binary search.
            for i in range(len(candidate_maxes)):
                if elem < candidate_maxes[i]:
                    candidate_maxes[i] = elem
                    if i > 0:
                        predecessor[elem] = candidate_maxes[i-1]
                    break
                i -= 1

    elem = candidate_maxes[-1]
    result = [elem]
    while elem in predecessor:
        elem = predecessor[elem]
        result.append(elem)
    result.reverse()
    return result

test()

#include <iostream>
#include <cmath>
#include <vector>
#include <ext/hash_map>
using namespace std;

int merge(__gnu_cxx::hash_map<int, int>& map, int left, int right)
{
int newMax = map[left] + map[right];
map[left] = newMax;
map[right] = newMax;
return newMax;
}

int findLongestSequence(vector<int>& a)
{
int max = 0;
__gnu_cxx::hash_map<int, int> map;

for (int i = 0; i < a.size(); i++)
{
if (map[a[i]]) continue;

map[a[i]] = 1;
// update the neighbours
if (map[(a[i]-1)]) //left neighbor
{
int retval = merge(map, a[i]-1, a[i]);
if (retval > max) max = retval;
}

if (map[a[i]+1]) // right neighbor
{
int retval = merge(map, a[i], a[i]+1);
if (retval > max) max = retval;
}
}
return max;
}

int main()
{
vector<int> b(5);
b[0] = 6;
b[1] = 55;
b[2] = 5;
b[3] = 4;
b[4] = 3;
b[5] = 99;

int ret = findLongestSequence(b);
cout << "ret = " << ret << endl;

//expect = 4

}

The possible reason that someone (not me) to down vote this one might be the wrong output. But anyway this is well-know problem "Longest increasing subsequence" you can google it. The complexity is O(nlogn). Beware it is not easy to make it right. This is mine version

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

#define STRICTLY_INCREASING 1
template<typename T>
std::vector<T> LIS(const std::vector<T>& v) {
    typedef T                               value_type;
    typedef std::pair<value_type, int>      value_pos_type;
    typedef std::vector< value_pos_type >   value_pos_vector_type;
    typedef typename value_pos_vector_type::iterator best_iterator_type;
    
    size_t n = v.size();
    std::vector<int> p(n);
    
    std::vector< value_pos_type > best;
    value_pos_type cur = std::make_pair(std::numeric_limits<value_type>::min(), -1);
    best.push_back(cur);
    
    for (int i=0; i< n; ++i) {
#ifdef STRICTLY_INCREASING
        value_pos_type cur = std::make_pair(v[i], 0);
        best_iterator_type it = lower_bound(best.begin(), best.end(), cur);
        cur.second = i;
#else
        value_pos_type cur = std::make_pair(v[i], i);
        best_iterator_type it = upper_bound(best.begin(), best.end(), cur);
#endif   

        if (it == best.end()) {
            p[i] = best.back().second;
            best.push_back(cur);
        } else {
            best_iterator_type pIt = it-1;
            p[i] = pIt->second;
            *it = cur;
        }
    }

    std::vector<value_type> ret(best.size() - 1);
    int f = best.back().second;
    for (int i = ret.size()-1; i >=0; --i) {
        ret[i] = v[f];
        f = p[f];
    }
    return ret;
}

int main(int agrc, char** argv) {
    int a[] = {5,6,3,4,1,9,9,8,9,5 };
    //int a[]  = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    std::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
    std::vector<int> res = LIS(v);

    for (int i=0; i < res.size(); ++i )
        std::cout << res[i] << ' ';
    std::cout << std::endl;
}

Code

// Binary search
int GetCeilIndex(int A[], int T[], int l, int r, int key) {
   int m;
 
   while( r - l > 1 ) {
      m = l + (r - l)/2;
      if( A[T[m]] >= key )
         r = m;
      else
         l = m;
   }
 
   return r;
}
 
int LongestIncreasingSubsequence(int A[], int size) {
 
   int *tailIndices = new int[size];
   int *prevIndices = new int[size];
   int len;
 
   memset(tailIndices, 0, sizeof(tailIndices[0])*size);
   memset(prevIndices, 0xFF, sizeof(prevIndices[0])*size);
 
   tailIndices[0] = 0;
   prevIndices[0] = -1;
   len = 1; // it will always point to empty location
   for( int i = 1; i < size; i++ ) {
      if( A[i] < A[tailIndices[0]] ) {
         // new smallest value
         tailIndices[0] = i;
      } else if( A[i] > A[tailIndices[len-1]] ) {
         // A[i] wants to extend largest subsequence
         prevIndices[i] = tailIndices[len-1];
         tailIndices[len++] = i;
      } else {
         // A[i] wants to be a potential condidate of future subsequence
         // It will replace ceil value in tailIndices
        int pos = GetCeilIndex(A, tailIndices, -1, len-1, A[i]);
 
        prevIndices[i] = tailIndices[pos-1];
        tailIndices[pos] = i;
      }
   }
   cout << "LIS of given input" << endl;
   for( int i = tailIndices[len-1]; i >= 0; i = prevIndices[i] )
      cout << A[i] << "   ";
   cout << endl;
 
   delete[] tailIndices;
   delete[] prevIndices;
 
   return len;
}

#include <iostream>
#include <string.h>
#include <stdio.h>
 
using namespace std;
 
#define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])
// Binary search (note boundaries in the caller)
// A[] is ceilIndex in the caller
int CeilIndex(int *A, int *table, int l, int r, int key) {
    int m;
 
    while( r-l > 1 ) {
        m = l + (r-l)/2;
        (A[table[m]] >= A[key] ? r : l) = m; // ternary expression returns an l-value
    }
 
    return r;
}
 
int LongestIncreasingSubsequenceLength(int A[], int size, int *result) {
    // Add boundary case, when array size is one
 
    int *tailTable   = new int[size];
    int *parentIndex = new int[size];
    int len, pos; // always points empty slot
 	int i;
    memset(tailTable, 0, sizeof(tailTable[0])*size);
    memset(parentIndex, -1, sizeof(parentIndex[0])*size);
    tailTable[0] = 0;
    len = 1;
    for(i = 1; i < size; i++ ) {
        if( A[i] < A[tailTable[0]] )
            // new smallest value
            {
			   	   tailTable[0] = i;
				   parentIndex[i] = -1;
			}
	    else if( A[i] > A[tailTable[len-1]] )
            // A[i] wants to extend largest subsequence
            {
			   		tailTable[len] = i;
			   		parentIndex[i]=tailTable[len-1];
					len++;   	
			}
        else
            // A[i] wants to be current end candidate of an existing subsequence
            // It will replace ceil value in tailTable
            {
			   	  pos= CeilIndex(A, tailTable, -1, len-1, i);
			   	  tailTable[pos] = i;
				  parentIndex[i]=tailTable[pos-1];
		    }
            
    }
 	i=tailTable[len-1];
 	for (int j=len-1;j>=0 && i!=-1;j--){
		result[j]=A[i];
		i=parentIndex[i];
	}
    delete[] tailTable;
    delete[] parentIndex;
    return len;
}
 
int main() {
    //int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
    int A[] = {5,2,6,3,4,1,9,8,9,5,6,7};
    int n = ARRAY_SIZE(A);
    int x;
    int *result= new int[n]; 
    printf("Length of Longest Increasing Subsequence is %d\n",
            x=LongestIncreasingSubsequenceLength(A, n, result));
   	cout<<"result"<<endl;
	for(int i=0;i<x;i++)
	  cout<<result[i]<<" ";
    cout<<endl;    
    return 0;
}

use a max heap data structure so only maximum elements will be there in the heap...

use a min heap....