c# - 最长排序子序列的长度

Question

我的未排序数组是

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

在这个数组中，10,22,33,50,60,80按升序排列，所以输出必须是 6。

一般来说，我希望由数组元素组成并从第一个元素开始的升序列表的最长可能长度。

我已经试过了:

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;

但没有成功。

Answer 1

这叫做 Longest Ascending Subsequence问题。您可以使用本文中描述的简单动态规划算法找到它。

如果你只需要最长子序列的长度，你可以这样做:

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

您的算法不正确，因为它使用了“贪心策略”，即它认为任何大于先前找到的数字的数字都是已排序序列的一部分。