8

配列の最大サブ配列の問題を解決するために、Kadaneのアルゴリズムを次のように実装しています。

public static decimal FindBestSubsequence
    (this IEnumerable<decimal> source, out int startIndex, out int endIndex)
{
    decimal result = decimal.MinValue;
    decimal sum = 0;
    int tempStart = 0;

    List<decimal> tempList = new List<decimal>(source);

    startIndex = 0;
    endIndex = 0;

    for (int index = 0; index < tempList.Count; index++)
    {
        sum += tempList[index];
        if ((sum > result) || 
            (sum == result && (endIndex - startIndex) < (index - tempStart)))
        {
            result = sum;
            startIndex = tempStart;
            endIndex = index;
        }
        else if (sum < 0)
        {
            sum = 0;
            tempStart = index + 1;
        }
    }

    return result;
}

の代わりにの-1, 2, 3結果を与えるように、負の数で始まるシーケンスを使用すると失敗します。4, [0,2]5, [1,2]

エラーがどこにあるのかわからない私の人生のために。多分それはアルゴリズム設計の欠陥ですか？

前もって感謝します。

4

6 に答える 6

8

最初の実装では、メインのスキャンサイクル内で、不必要に複雑で部分的に間違ったチェックが発生していました。これらのチェックは2つです。

  • より大きな中間体sumが見つかった場合は、一時的な結果としてその構成要素を保存します。
  • 独立して、sum負になった場合は、にリセットして0、次のスキャン位置から新しいシーケンスを作成する準備をします。

リファクタリングFindBestSubsequenceされたメソッドの実装を以下に示します。

public static decimal FindBestSubsequence (this IEnumerable<decimal> source, out int startIndex, out int endIndex)
{
    decimal result = decimal.MinValue;
    decimal sum = 0;
    int tempStart = 0;

    List<decimal> tempList = new List<decimal>(source);

    startIndex = 0;
    endIndex = 0;

    for (int index = 0; index < tempList.Count; index++)
    {
        sum += tempList[index];
        if (sum > result)
        {
            result = sum;
            startIndex = tempStart;
            endIndex = index;
        }
        if (sum < 0)
        {
            sum = 0;
            tempStart = index + 1;
        }
    }

    return result;
}

-1,2,3これで、上記のコードに対して正しい答えが生成されるだけで5,[1,2]なく、余分なコードなしですべての負の数の配列が正しく処理されます。入力-10,-2,-3すると。が返され-2,[1,1]ます。

于 2012-03-27T16:22:40.980 に答える
3

あなたの例では、ループの最初の反復であってsum > resultも、常に持っています。sum<00 > decimal.MinValue

したがって、2番目のケースに進むことはありません。-

条件を追加する場合は、最初に変更する必要がありますsum > 0。

if ((sum >0 ) & ((sum > result) || 
    (sum == result && (endIndex - startIndex) < (index - tempStart))))
{
    ...
}
else if (sum < 0)
{
    ...
}

アップデート：

私のコメントで説明されているように、結果の初期化を0に変更することができます：

decimal result = 0;

ウィキペディアから：

このサブアレイは空であるか（この場合、その合計はゼロです）、前の位置で終了する最大サブアレイより1つ多い要素で構成されています。

したがって、配列に負の数のみが含まれている場合、解は合計が0の空のサブ配列になります。

于 2012-03-27T13:22:40.107 に答える
1

この行を変更します。

decimal result = decimal.MinValue;

に

decimal result = 0;
于 2012-03-27T13:36:58.850 に答える
0

位置ごとに、（元のシーケンスからの）値の最大値と、書き込んだ合計を取得する必要があります。元の数値が大きい場合は、「最初から」の合計を開始することをお勧めします。つまりsum = max(sum+tempList[index],tempList[index]);、合計が0未満の場合はまったく必要ありません。

于 2012-03-27T13:37:20.777 に答える
0

最後に、これは、誰かに役立つ場合に備えて、すべてのシナリオを処理するようにアルゴリズムを修正した方法です。

    public static decimal FindBestSubsequence (this IEnumerable<decimal> source, out int startIndex, out int endIndex)
    {
        decimal result = decimal.MinValue;
        decimal sum = 0;
        int tempStart = 0;

        List<decimal> tempList = new List<decimal>(source);

        if (tempList.TrueForAll(v => v <= 0))
        {
            result = tempList.Max();
            startIndex = endIndex = tempList.IndexOf(result);
        }
        else
        {
            startIndex = 0;
            endIndex = 0;

            for (int index = 0; index < tempList.Count; index++)
            {
                sum += tempList[index];

                if (sum > 0 && sum > result || (sum == result && (endIndex - startIndex) < (index - tempStart)))
                {
                    result = sum;
                    startIndex = tempStart;
                    endIndex = index;
                }
                else if (sum < 0)
                {
                    sum = 0;
                    tempStart = index + 1;
                }
            }
        }

        return result;
    }
于 2012-03-27T16:12:00.437 に答える
0

ジーンベリツキの答えとコメントに基づいて構築：

    public static void Main()
    {
        var seq = new[] { -10M, -2M, -3M };
        var stuff = seq.FindBestSubsequence();

        Console.WriteLine(stuff.Item1 + " " + stuff.Item2 + " " + stuff.Item3);
        Console.ReadLine();
    }

    public static Tuple<decimal, long, long> FindBestSubsequence(this IEnumerable<decimal> source)
    {
        var result = new Tuple<decimal, long, long>(decimal.MinValue, -1L, -1L);

        if (source == null)
        {
            return result;
        }

        var sum = 0M;
        var tempStart = 0L;
        var index = 0L;

        foreach (var item in source)
        {
            sum += item;
            if (sum > result.Item1)
            {
                result = new Tuple<decimal, long, long>(sum, tempStart, index);
            }

            if (sum < 0)
            {
                sum = 0;
                tempStart = index + 1;
            }

            index++;
        }

        return result;
    }
于 2012-04-05T15:47:23.337 に答える