Советы по дальнейшей оптимизации решения DP

Question

Я решил вопрос о самой длинной возрастающей подпоследовательности на LeetCode: https://leetcode.com/problems/longest-increasing-subsequence/

Учитывая несортированный массив целых чисел, найдите длину самой длинной возрастающей подпоследовательности. Для [10,9,2,5,3,7,101,18] ответ будет 4 (размер [2,3,7,101]).

class Solution {
public:
    int helper(vector<int>& nums, unordered_map<int, vector<int>>& dp, int lastNum, int startIndex) {
        if(startIndex>=nums.size()) return 0;
        if(dp.find(lastNum)!=dp.end() && dp[lastNum].size()>=startIndex && dp[lastNum][startIndex]!=INT_MIN) {
            return dp[lastNum][startIndex];
        }
        
        int ans=0;
        if(nums[startIndex]>lastNum) ans=1+helper(nums, dp, nums[startIndex], startIndex+1);
        ans=max(ans, helper(nums, dp, lastNum, startIndex+1));
        
        return dp[lastNum][startIndex]=ans;
    }
    
    int lengthOfLIS(vector<int>& nums) {
        int ans=0;
        unordered_map<int, vector<int>> dp;
        dp[INT_MIN].resize(10001, INT_MIN);
        for(int i=0; i<nums.size(); i++) dp[nums[i]].resize(10001, INT_MIN);
        
        return helper(nums, dp, INT_MIN, 0);
    }
};

Обратите внимание, что я также запоминаю его, используя таблицу dp выше и использую два состояния lastNum (nums[i] значение, которое мы выбрали в последней рекурсии) и startIndex. В разделе решения они используют два состояния prev ( индекс , в отличие от значение , которое я передаю с помощью lastNum) и curpos (аналогично startIndex).

Я сбит с толку, потому что у меня все еще есть TLE. Теперь я знаю, что временные ограничения, установленные онлайн-судьями, произвольны, но я хочу понять, почему использование lastNum вместо prev в качестве состояния приводит к увеличению времени выполнения. Точно так же, есть ли какие-либо другие оптимизации, которые я могу сделать?

Спасибо!

Изменить: я изменил его на 10001, на основе предложения Игоря в комментариях, все тесты проходят сейчас , но это занимает много времени:

24/24 тестовые примеры пройдены, но заняли слишком много времени.

Edit2: Другими словами, я думаю, мой вопрос: Как интервьюер, какой совет можно дать, чтобы подтолкнуть кандидата в правильном направлении (использовать prev вместо lastNum)?

Answer 1

Не уверен в вашем решении, но я здесь немного озадачен: dp[INT_MIN].resize(10000001, INT_MIN);, возможно, ваше решение не O (N). Это будет принято:

#include <vector>
#include <algorithm>

struct Solution {
    static const inline int lengthOfLIS(const std::vector<int> &nums) {
        std::vector<int> longest;

        for (unsigned int index = 0; index < nums.size(); index++) {
            const auto iter = std::lower_bound(longest.begin(), longest.end(), nums[index]);

            if (iter == longest.end()) {
                longest.emplace_back(nums[index]);

            } else {
                *iter = nums[index];
            }
        }

        return longest.size();
    }
};

Ссылки

• Дополнительные сведения см. На Доске обсуждения . Существует множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптот c время / пространство анализ сложности ^{1 , 2} там.

Если вы готовитесь к собеседованию :

• Мы хотели бы написать коды без ошибок и чистые на основе стандартов и соглашений (например, c ^{1 , 2} , c ++ ^{1 , 2} , java ^{1 , 2} , c# ^{1 , 2} , python ¹ , javascript ¹ , go ¹ , ржавчина ¹ ).

Answer 2

На основе http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

 int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if(it==res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
}