最长的排序序列长度 [英] Length of the longest sorted subsequence

问题描述

我的无序阵列

string[] a = new string[] { "10", "22", "9", "33", "21", "50", "41", "60", "80" };

在此阵， 10,22,33,50,60,80 按升序排列，
所以输出必须 6 。

In this array, 10,22,33,50,60,80 are in ascending order, so the output must be 6.

在一般情况下，我想从阵列的元件制成，并与第一个元素开始升序列表的最长的可能长度。

In general, I want the longest possible length of an ascending list made from elements of the array and starting with the first element.

我已经试过这样：

string[] a = new string[] { "10", "22", "9", "33", "21", "50", "41", "60", "80" };
List<int> res = new List<int>();
int arrLength = a.Length;
int i = 0;
int prev;
while (i < arrLength)
{
    if (i < arrLength)
    {
        res.Add(Convert.ToInt32(a[i]));
        prev = Convert.ToInt32(a[i]);
        while (Convert.ToInt32(a[++i]) < prev) { }
    }
}

int asdf = res.Count;

但没成功。

推荐答案

这就是所谓的的最长升序子序列的问题。您可以使用本文中介绍一个简单的动态规划算法找到它。

This is called the Longest Ascending Subsequence problem. You can find it using a simple dynamic programming algorithm described in the article.

如果你需要的是时间最长的子序列的长度，你可以做这样的：

If all you need is the length of the longest subsequence, you can do it like this:

// length[i] is the length of subsequence ending at position i
var length = new int[a.Length];
for (var i = 0 ; i != length.Length ; i++) {
    // In the worst case a number ends a subsequence of length 1
    length[i] = 1;
    var ai = Convert.ToInt32(a[i]);
    // Go backward on the items that we've seen before
    for (var j = i-1 ; j >= 0 ; j--) {
        var aj = Convert.ToInt32(a[i]);
        // If number at i is greater than the number at j, use the length of j's longest subsequence
        // to calculate the length of the sequence for element at i.
        if (aj > ai && length[j]+1 > length[i]) {
            length[i] = length[j]+1;
        }
    }
}
var res = length.Max();

您算法不正确，因为它采用了贪婪策略，即认为它比$ P $的任何数字pviously发现了一个排序序列的一部分。

Your algorithm is incorrect because it uses a "greedy strategy", i.e. it considers any number greater than the previously found one a part of the sorted sequence.

这篇关于最长的排序序列长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！