首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >这个算法对于寻找最长的递增子序列是正确的吗?

这个算法对于寻找最长的递增子序列是正确的吗?
EN

Stack Overflow用户
提问于 2015-03-16 06:55:03
回答 1查看 108关注 0票数 1

我收到一个未排序的数组,我需要找到最长的递增子序列。根据Wikipedia的说法,最有效的算法是O(nlogn),这是O(n),所以我肯定做了一些愚蠢的错误

代码语言:javascript
复制
public static int[] longestAscending(int[] arr) {
        // {x /* starting index */, y /* ending index */};
        int[] max = {0, 0};
        int[] current = {0,1};

        for (int i=1; i<arr.length; i++) {
            if (arr[i-1] < arr[i]) {
                current[1]++;
                if (current[1] - current[0] > max[1] - max[0]) {
                    max[0] = current[0];
                    max[1] = current[1];
                }
            } else {
                current[0] = i;
                current[1] = i + 1;
            }
        }

        return max;
    }
EN

回答 1

Stack Overflow用户

发布于 2015-03-16 07:00:49

您的算法只检测连续的子序列,而不检测有间隙的子序列。例如:

代码语言:javascript
复制
1 9 2 3

这里最长的递增子序列是1 2 3,您的算法找不到它。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/29067188

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档