1

任务如下：

1）输入=“n”个数字的序列（n - 正数，数字 - 没有限制）

2）目标：提取最长的非递减子序列。如果两个或更多子序列具有相同的长度 - 打印最左边的。

示例：输入 = 7 3 5 8 -1 6 7，输出 = 3 5 6 7

现在在头疼了一整天的时候，我遇到了两个主要问题。首先是编写一个算法，存储输入序列中所有可能的非递减子序列。第二个是想出一个最优的方法来测量所有的子序列并打印出最左边最长的。这是我目前所在的位置：

using System;

class LongestNonDecreasingSequence
{
    static void Main()
    {
        string input = Console.ReadLine();
        string[] chars = input.Split(' ');
        int[] numbers = new int[input.Length];
        int n = chars.Length;
        for(int i = 0; i < n; i++)
        {
            numbers[i] = int.Parse(chars[i]);
        }
        int[,] matrix = new int[n, n];
        for(int column = 0; column < n; column++)
        {
            for(int row = column, rowMatrix = 0; row < n; row++)
            {
                if(numbers[column] <= numbers[row])
                {
                    matrix[column, rowMatrix] = numbers[row];
                    rowMatrix++;
                }
            }
        }
        for(int column = 0; column < n; column++)
        {
            for(int row = 1; row < n; row++)
            {
                if(matrix[column, row] < matrix[column, row - 1] && /* ?Condition */)
                {
                    /* Remove ?elements */
                }
                /* ?Remove rows, cointaining zero value */
            }
        }
        int[] matrixLengths = new int[n];
        for(int column = 0; column < n; column++)
        {
            matrixLengths[column] = matrix.GetLength(1);
        }   
    }
}

我有一个二维数组，将每个子序列存储在一个新列中。在我们的示例中 - 7 3 5 8 -1 6 7；在第 0 列中，我们存储 7，第 1 - 7 列 8，第 2 - 3 列 5 8 6 7，第 3 - 5 列 8 6 7，第 4 - 8 列，第 5 - -1 列 6 7，第 6 - 6 列 7，列7 - 7;

现在问题1）在每个子序列中删除数字，不符合条件。在我们的例子中：第 2 列 - 3 5 6 7，第 3 列 - 5 6 7；

现在问题 2) 按 Array.Length 比较所有列 (1 - 7) 并获得最高值。

我仍然无法弄清楚问题 1 的算法。对于问题 2，我只需要知道如何测量二维数组中每个单独列的长度。从我过去几个小时一直在阅读的内容来看，也许我必须使用锯齿状数组，而不是 2D。那么获得每列的长度会更容易吗？在 for 循环中定义每个下一个锯齿状数组（每列的数组）会比较棘手，但我认为我可以使用字符串来保存我的数字，然后使用 '.Split' 为数组赋值。

我希望我表达得足够清楚。如果不是这种情况，请通知我，以便我指定。非常欢迎对这两个问题提出任何建议和信息。

谢谢！

4

0 回答 0