最长排序子序列的长度

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;

但未成功。

- Prashant16

Answer 1

这被称为最长上升子序列问题。你可以使用文章中描述的简单动态规划算法找到它。

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

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

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

- Sergey Kalinichenko

---

这看起来不对：for (var j = i-1 ; j >= 0 ; j++)。那应该是在递减 j 吗？ - John H

我认为这可以更容易地解决（只需一个循环）。 - Fabian Bigler

@dasblinkenlight，我也回答了这个问题。你不觉得这样更快吗？ - Fabian Bigler

@dasblinkenlight 啊不对，我以为你要在每个子序列后重新开始计数。但实际上是将它们加起来。我的错。 - Fabian Bigler

@RameshRajendran 通过“最长”递增序列，我们实际上是在寻找可能的最长序列。1, 100不是该数据集中的最长序列。1, 2, 3, 4, 5才是。 - John H

Answer 2

作业？这是一个可以使用动态规划解决的问题的典型例子。数组longest将保存以相同位置的元素结尾的最长递增子序列。

public int LongestIncreasingSubseries(int[] input)
{
  int[] longest = new int[input.Length];
  int result = 1;
  for(int i = 0; i<input.Length; ++i) 
  {
    longest[i] = 1;
    for(j=0; j<i; ++j) if (input[j]<input[i] && longest[j]+1>longest[i]) longest[i] = longest[j]+1;
    if(longest[j]>result) result = longest[i];
  }
  return result;
}

- Grzenio

Answer 3

string[] arr = new string[] { "10", "22", "9", "33", "21", "50", "41", "60", "80" };
int biggest = int.MinValue;
int current = 0;

int count = (from str in arr
             where int.TryParse(str, out current)
             let number = current
             where number > biggest
             select biggest = number).Count();

这个LINQ查询将每个字符串尝试转换为数字。如果成功，它会检查该数字是否大于上一个最大数字。如果是，则将该数字存储为新的最大数字，并返回它。

Count方法只计算返回的项数（但您可以将它们存储在数组中，在foreach循环中迭代或执行其他任何操作）。

- Shlomi Borovitz

Answer 4

这是我的答案。

我很容易理解你。

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;
        for (i = 0; i < arrLength; i++)
        {
            if (i < arrLength)
            {
                if (res.Count != 0)
                {
                    if (Convert.ToInt32(a[i]) > res[res.Count - 1])
                    {
                        res.Add(Convert.ToInt32(a[i]));
                    }
                }
                else
                {
                    res.Add(Convert.ToInt32(a[i]));
                }
            }
        }

        int asdf = res.Count;

输出结果为6

请查看此

你可以在这里下载我的代码

- Ramesh Rajendran

---

请不要在评论中告诉别人去阅读你的答案。这是垃圾信息，也不合适。请阅读有关评论的规则（http://stackoverflow.com/help/privileges/comment）- 评论应该让其他人知道临时问题（例如，“有一个错误需要修复”）或提出小的后续问题（例如，“你的第二句话不清楚，你是指<这个>还是<那个>？”）。 - Gilles 'SO- stop being evil'

Answer 5

即使您成功地将其计数，仍可能会遇到此问题。

如果有多个有序值集要发现，您想要同时发现两个还是只发现第一个或以最低数字开头的那个等等？

首先需要做的是将数组复制到所需的顺序中。然后，您需要对无序数组执行检查，循环并将值与有序数组进行比较，并在排序停止时退出循环。但您仍然需要考虑从中获取哪些数据以及将其包含在代码中。

- BenM