c++ - 进一步优化DP解决方案的提示

Question

我在LeetCode上解决了最长递增子序列问题:https://leetcode.com/problems/longest-increasing-subsequence/

Given an unsorted array of integers, find the length of longest increasing subsequence. For [10,9,2,5,3,7,101,18], the answer is 4 (size of [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来记住它。在 solution section中，它们使用两种状态 prev(索引，与我使用 lastNum传递的值不同)和 curpos(类似于 startIndex)。
我很困惑，因为我仍然获得TLE。现在，我知道在线法官设置的时间限制是任意的，但我希望了解为什么使用 lastNum而不是 prev作为状态会导致更多的执行时间。同样，我还能进行其他优化吗？
谢谢!
编辑:根据评论中Igor的建议，我将其更改为 10001，所有测试用例现在都通过了，但是需要很多时间:

24 / 24 test cases passed, but took too long.

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

引用文献

有关更多详细信息，请参见Discussion Board。那里有很多接受的解决方案，其中包含各种languages和说明，高效的算法以及渐近time / space复杂度分析1，2。

如果您正在准备 interviews:

我们希望基于标准和约定来编写bug-free和clean代码(例如c 1，2，c++ 1，2，java 1，2，c# _1，2 _python，1 _javascript， 。