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

宿題？これは、動的計画法を使用して解決できる問題の教科書的な例です。配列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 に答える
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

これが私の答えです。

あなたを理解するのは簡単です

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

manager を実行して正しくカウントする場合でも、これで問題が発生する可能性があります。

検出する順序付けられた値のセットが複数ある場合、両方を検出するか、最初の値のみを検出するか、最小の数値から始まる値などを検出しますか?

最初に行う必要があるのは、配列を取得し、必要な順序でそのコピーを作成することです。次に、順序付けされていない配列に対してチェックを実行し、値を順序付けられた配列と比較して比較し、順序付けが停​​止したときにループを抜け出す必要があります。ただし、これを実行して取得したいデータの他の側面を考慮し、それをコードに含める必要があります。

于 2014-03-04T11:19:59.303 に答える