Нахождение самого большого отсортированного выбора

Question

Пример: учитывая [1 2 3 10 7 8 9], я ищу алгоритм, дающий [1 1 1 0 1 1 1].

У меня есть несортированный массив в качестве ввода. В качестве вывода я ищу самый большой отсортированный выбор.

• Под "выделением" я подразумеваю массив одинаковой длины, содержащий 1 с и 0 с (если элементы выбраны или нет).
• Под "отсортированным" я подразумеваю, что выбранные элементы составляют отсортированный массив - в приведенном выше примере: [1 2 3 7 8 9].
• И под "самым большим" я подразумеваю, что нет отсортированного выбора, который имеет больше 1 в нем.

В худшем случае: я должен попробовать все 2^{0,1} возможных выборов. Есть ли более быстрый алгоритм для этого? Я не помню ни одного из исследования CS и не мог найти ничего онлайн (по крайней мере, с моей формулировкой).

Answer 1

Да, это можно решить с помощью динамического программирования.

Вы должны создать еще один массив пары длины, равной данному массиву, назовем его arr

arr [index] будет хранить максимальную длину подмассива, так что данный Array[индекс] является последним элементом в отсортированном порядке, если массив рассматривается из данного массива [0... индекс] и элемента, после которого добавляется данный массив [индекс].

Из arr вы можете найти максимальную длину отсортированного массива и создать массив.

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;
}

сложность: n*n

Answer 2

Здесь я написал метод largeSortedSelection, который принимает вектор элементов в качестве входных данных (например, как [1 2 3 10 7 8 9]) и возвращает логический вектор с true/false, представляющим 1/0, указывающий выбор индекса в ответе или нет (например, как [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;
}

В этом методе:

• selectedLen (i): наибольшая длина отсортированного списка, заканчивающаяся индексом-i.

• sortedList: содержит элементы в отсортированной возрастающей форме.

• Выбор: содержит ответ в виде 0/1
• Функция lower_bound в sortedList: возвращает первый элемент, который больше или равен.

Дайте мне знать, если вы чувствуете трудности в понимании исходного кода.
Как я использовал функцию lower_bound (которая имеет сложность logN) N раз в цикле. Итак, общая сложность времени: O (N logN).
Сложность памяти будет O(N), так как я использую память для хранения N элементов.

Answer 3

Спасибо всем за помощь. Это реализация C++ псевдокода Википедии, с которой я закончил:

/// 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;
}

Чтобы получить вектор истинности / ложности, нужно:

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