3

我的未排序数组是

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;

但没有成功。

4

5 回答 5

4

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

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.

于 2014-03-04T11:18:38.080 回答
0

这是我的回答。

很容易理解你

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

看到这个短屏幕

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

于 2014-03-04T11:41:28.027 回答
0 
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 循环中迭代它们，或其他任何东西）。

于 2014-03-04T11:39:39.587 回答
0

即使您执行 manager 以使其正确计数，您也可能会遇到问题。

如果要发现多个有序值集怎么办，您是要发现两者还是只发现第一个值或以最小数字开头的值等？

您首先需要做的是获取数组并按照您需要的顺序创建它的副本。然后，您需要对循环遍历的无序数组执行检查，并将值与有序数组进行比较，并在排序停止时中断循环。但是您仍然需要考虑您希望从中获取哪些数据的其他方面，并将其包含在您的代码中。

于 2014-03-04T11:19:59.303 回答
0

家庭作业？这是可以使用动态规划解决的问题的教科书示例。该数组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;
}
于 2014-03-04T11:23:02.003 回答