Самая длинная увеличивающаяся и уменьшающаяся подпоследовательность (сверху вниз с памяткой)

Question

Вопрос. Для массива целых чисел A длины N найдите длину самой длинной подпоследовательности, которая сначала увеличивается, а затем уменьшается. Ввод: [1, 11, 2, 10, 4, 5, 2, 1]

Выход: 6

Объяснение: [1 2 10 4 2 1] - самая длинная подпоследовательность.

Я написал нисходящий подход. У меня есть пять аргументов - вектор A (содержащий последовательность), начальный индекс (обозначающий текущий индекс), предыдущее значение, большое (обозначающее максимальное значение в текущей подпоследовательности) и map (m) STL.

Для возврата Подход У меня есть два случая -

1. элемент исключен - В этом случае мы переходим к следующему элементу (начало + 1). prev и large остаются прежними.

2. элемент включен - имеет два корпуса

   a. если текущее значение (A [start]) больше, чем prev и prev == large, то это случай возрастающей последовательности. Тогда уравнение становится 1 + LS (start + 1, A [start], A [start]), т.е. prev становится текущим элементом (A [start]), а самый большой элемент также становится A [start].

   b. если текущее значение (A [start]) меньше, чем prev, а current (A [start]) <большое, то это случай убывающей последовательности. Тогда уравнение становится 1 + LS (начало + 1, A [начало], большое), т.е. prev становится текущим элементом (A [начало]), а самый большой элемент остается тем же, то есть большим. </p>

Base Случаи -

1. , если текущий индекс находится вне массива, т.е. start == end, затем возвращает 0.

2. , если последовательность уменьшается, а затем увеличивается затем верните 0. т.е. если (текущий> предыдущий и предыдущий <максимальное значение), затем верните 0. </p>

Это не оптимизированный подход, так как map.find () сам по себе является дорогостоящей операцией , Может кто-нибудь предложить оптимизированный нисходящий подход с запоминанием.

int LS(const vector<int> &A, int start, int end, int prev, int large, map<string, int>&m){

    if(start == end){return 0;}
    if(A[start] > prev && prev < large){
        return 0;
    }

    string key = to_string(start) + '|' + to_string(prev) + '|' + to_string(large);

    if(m.find(key) == m.end()){
        int excl = LS(A, start+1, end, prev, large, m);
        int incl = 0;
        if(((A[start] > prev)&&(prev==large))){
            incl = 1 + LS(A, start+1, end, A[start],A[start], m); 
        }else if(((A[start]<prev)&&(A[start]<large))){
            incl = 1+ LS(A, start+1, end, A[start], large, m);
        }  

        m[key] = max(incl, excl);
    }

    return m[key];
}

int Solution::longestSubsequenceLength(const vector<int> &A) {
        map<string, int>m;
        return LS(A, 0, A.size(), INT_MIN, INT_MIN, m);
}

Answer 1

Не уверен насчет нисходящего, но, похоже, мы могли бы использовать алгоритм classi c LIS , чтобы просто подойти к каждому элементу с «обеих сторон» как бы. Вот пример с каждым элементом как самый правый и самый левый соответственно, поскольку мы выполняем итерацию в обоих направлениях. Мы можем видеть три экземпляра правильной последовательности длиной 6:

[1, 11, 2, 10, 4, 5, 2, 1]

 1 11       11 10 4 2 1
 1 2                2 1
 1 2 10        10 4 2 1
 1 2 4            4 2 1
 1 2 4 5          5 2 1
 1 2                2 1