Finding largest sorted selection

Question

Example: Given [1 2 3 10 7 8 9], I look for an algorithm giving [1 1 1 0 1 1 1].

I have an unsorted array as input. As output I look for a largest sorted selection.

With "selection" I mean an array of the same length holding 1s and 0s (if the elements are selected or not).
With "sorted" I mean that the selected elements make a sorted array - in the above example: [1 2 3 7 8 9].
And with "a largest" I mean that there is no sorted selection that has more 1s in it.

Worst case: I have to try all 2^{0,1} possible selections. Is there a faster algorithm to do that? I dont't remember any from CS study and could not find anything online (at least with my wording).

This is better known as the [longest increasing subsequence problem](https://en.wikipedia.org/wiki/Longest_increasing_subsequence). — user2357112, Jul 08 '18 at 09:41
read about it here https://www.geeksforgeeks.org/longest-increasing-subsequence/ — Ofir G, Jul 08 '18 at 09:56
Possible duplicate of [How to determine the longest increasing subsequence using dynamic programming?](https://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming) — , Jul 08 '18 at 11:59
Wikipedia helped, thanks! The geeksforgeeks site only details the O(N^2) solution. The other stackoverflow-post confused me a little with S vs LIS. I now implemented the Wikipedia-version and post it here. — user1239014, Jul 10 '18 at 07:39

score 1 · Answer 1 · answered Jul 08 '18 at 09:37

Yes, This can be solved via Dynamic Programming.

You have to create another array of pair of length equal to the given array let us name it as arr

arr[index] will store the maximum length of the subarray such that givenArray[index] is the last element in sorted order if array is considered from givenArray[0...index] and the element after which givenArray[index] is added.

From arr you can find the maximum length of the sub sorted array and create the array.

for (int i = 0;i<givenArray.size(); i++) {

    int after = -1;
    int length = 0;
    for(int j = 0;j<i;j++) {
        if (givenArray[j] < givenArray[i] && length < arr[j].maxLengthTillNow) {
            length = arr[j].maxLengthTillNow;
            after = j;
        }
    }

    arr[i].maxLengthTillNow = length + 1;
    arr[i].after = j;
}

complexity: n*n

That's unnecessarily high complexity, though. – user2357112 Jul 09 '18 at 17:09 — user2357112, Jul 09 '18 at 17:09

score 0 · Answer 2 · answered Jul 10 '18 at 06:07

Here, I have written a method largestSortedSelection which takes vector of elements as input ( like as [1 2 3 10 7 8 9] ) and returns Boolean vector with true/false representing 1/0 indicating selection of index in answer or not ( like as [1 1 1 0 1 1 1] ).

vector< bool >largestSortedSelection( vector<int>&v ){
int n = v.size(); 
vector< int >selectedLen(n);
vector< int >sortedList;
int maxLen = 1;
for(int i = 0; i<n; ++i){
    int lb = lower_bound(sortedList.begin(),sortedList.end(),v[i])-sortedList.begin();
    if( lb!=(int)sortedList.size() ){
        selectedLen[i]=lb+1;
        sortedList[lb]=v[i];
    }
    else {
        sortedList.push_back(v[i]);
        selectedLen[i]=(int)sortedList.size();
    }
    maxLen =  max( maxLen, selectedLen[i] );
}
int lst = INT_MAX;//assuming maximum element will be less than INT_MAX
int len = maxLen+1;
vector< bool >selection(n,0);
for(int i = n-1; i>=0; --i ){
    if( v[i]<lst && selectedLen[i]+1 == len ){
        selection[i] = 1;
        lst = v[i];
        len--;
    }
  }
  return selection;
}

In this method:

selectedLen(i) : longest length of sorted list ending upto index- i.
sortedList : holds the elements in sorted increasing form.
selection : holds the answer in the form of 0/1
lower_bound function in sortedList: returns first element that is greater-or-equal.

Let me know if you feel difficulty in understanding source code.
As I have used lower_bound function ( which is of complexity logN ) N times in a loop. So, overall time complexity is : O( N logN ).
Memory complexity will be O(N) as I am using memory for holding N elements.

For the input `vector v {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};` it seems to give a wrong result with just 0 and 2? — user1239014, Jul 10 '18 at 07:36
This algorithm returns : [1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1], indicating {0,2,6,9,11,15} as selected Sorted List. — BishalG, Jul 10 '18 at 07:44

score 0 · Answer 3 · answered Jul 10 '18 at 07:29

Thanks for everybodies help. This is the C++ implementation of the Wikipedia pseudocode I ended up with:

/// Return indice of the a longest increasing subsequence.
/// implementation of https://en.wikipedia.org/wiki/Longest_increasing_subsequence
template<class T>
std::vector<size_t> indiceOfLongesIncreasingSubsequence(const std::vector<T>& v)
{
  std::vector<size_t> P(v.size()), M(v.size() + 1);
  size_t L = 0;
  for(size_t i = 0; i < v.size(); ++i)
  {
    // binary search for the largest positive j <= L such that v[M[j]] < v[i]
    size_t lo = 1, hi = L;
    while(lo <= hi)
    {
      size_t mid = (lo + hi)/2;
      if(v[M[mid]] < v[i])
        lo = mid+1;
      else
        hi = mid-1;
    }

    // predecessor of v[i] is the last index of the subsequence of length lo-1
    P[i] = M[lo-1];
    M[lo] = i;

    if(lo > L)
      L = lo;
  }

  // reconstruct the longest increasing subsequence
  std::vector<size_t> ind(L);
  size_t k = M[L];
  for(size_t i = 0; i < L; ++i)
  {
    ind[L-1-i] = k;
    k = P[k];
  }

  return ind;
}

To get the true/false vector, one needs to:

vector<bool> selection(ind.size(), false);
for(size_t i: ind)
  selection[i] = true;

Finding largest sorted selection

3 Answers3