配列の最大サブ配列の問題を解決するために、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]
エラーがどこにあるのかわからない私の人生のために。多分それはアルゴリズム設計の欠陥ですか?
前もって感謝します。