标签: lis

我试图理解算法,它给出了时间O(n k log(n))中数组中长度K的增加子序列的数量.我知道如何使用O(k*n ^ 2)算法解决同样的问题.我查了一下,发现这个解决方案使用了BIT(Fenwick Tree)和DP.我也找到了一些代码,但我无法理解它.

以下是我访问过的一些有用的链接.

这里在SO
Topcoder论坛
随机网页

如果有人能帮助我理解这个算法,我真的很感激.

我实现了最长增加子序列(LIS)算法,因为我认为它会起作用,但结果完全是混乱的.

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = L[j]
        L[i].append(D[i])
    print L

返回结果:

[[3], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [1]]

应该是什么:

[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

正如我在调试器中看到的那样:

L[i] = L[j]

不仅L[i]获得新值 …

计算数组中的 LIS（最长递增子序列）是一个非常著名的动态规划问题。然而，在每个教程中，他们首先展示了不使用 DP 概念的递归解决方案，然后通过应用自底向上 DP（迭代解决方案）来解决它。

我的问题是：

我们将如何在 递归解决方案本身中使用记忆化。不只是记忆，而是使用一维数组记忆。

我做了一些研究，但找不到任何相关的东西。虽然有 2 个地方要求递归记忆1和 2但那边的解决方案是使用 2D Map / Array 进行记忆。

无论如何，用一维数组记住解决方案，会给出错误的输出。这是我所做的：

int lis(int idx, int prev)
{
    if(idx >= N)
        return 0;

    if(dp[idx])
        return dp[idx];

    int best_ans = lis(idx+1, prev);

    int cur_ans = 0;
    if(arr[idx] > prev)
    {
        cur_ans = 1 + lis(idx+1, arr[idx]);
    }
    int ans = max(best_ans, cur_ans);
    dp[idx] = ans;
    return ans;
}

int main()
{
    // Scan …

我试图找到一个数组的所有最长的增加子序列.我可以设法在维基百科上O(n log n)建议使用二进制搜索找到一个这样的LIS .

有人可以帮助我,我怎样才能找到所有这样的LIS.我找不到更好的方法来做到这一点O(n²).任何优化建议都会非常有用.

我最近在hyper-v上创建了一个全新的gen 2虚拟机,并安装了最近发布的ubuntu 14.04版本.

即使在apt-get更新之后,在启动时,我的Windows Server 2012 R2 Hyper-V服务器也会抱怨hyper-v事件日志中的下层驱动程序

合成显示驱动程序:'Dev Ubuntu 14.04 Gen2'中的设备'Microsoft Synthetic Display Controller'已加载但与服务器版本不同.服务器版本3.3客户端版本3.2(虚拟机ID 9FC171E7-B2C6-4BD2-9FF0-253209B2A69D).设备可以使用,但这是一种不受支持的配置.这意味着在解决此问题之前不会提供技术支持.要解决此问题,请升级集成服务.要升级,请连接到虚拟机,然后从"操作"菜单中选择"插入Integration Services安装盘".(当然这似乎不起作用)

和

数据交换集成服务:Hyper-V数据交换连接到虚拟机'Dev Ubuntu 14.04 Gen2',但版本与Hyper-V预期的版本不匹配(虚拟机ID 9FC171E7-B2C6-4BD2-9FF0-253209B2A69D).框架版本:谈判(3.0) - 预期(3.0); 消息版本:谈判(4.0) - 预期(5.0).这是一种不受支持的配置.这意味着在解决此问题之前不会提供技术支持.要解决此问题,请升级集成服务.要升级,请连接到虚拟机,然后从"操作"菜单中选择"插入Integration Services安装磁盘"(类似地,这似乎不起作用).

此外,hyper-v在使用Windows 2012 R2 hyper-V Manager的Summary选项卡中抱怨"Integration Services:需要更新".

我的(显然是错误的)信念是Linux Integration Services已经集成到内核中,因此Trusty将与2012 R2 hyper-v服务兼容.

任何人都可以解释在何处/如何获取14.04更新的Integration Services包和正确的安装过程,以便使用hyper-v 2012 r2完全支持我的ubuntu虚拟机？

非常感谢你的帮助,Doug Coleman

std::lower_bound和函数的复杂度是多少std::upper_bound。

我知道万一std::set<int>是这样log(n)，但我不知道std::vector<int>。

我正在使用向量 和 来实现最长递增子序列std::lower_bound。

这段代码的复杂度是多少？

int LIS2(vector<int> a) {
    vector<int> v;
    for (int i = 0; i < a.size(); i++) {
        auto it = lower_bound(v.begin(), v.end(), a[i]);
        if (it != v.end()) 
            *it = a[i];
        else 
            v.push_back(a[i]);
    }
    return v.size();
}