寻找最大连续子序列
给定一个实数序列X1,X2,...Xn(不需要是正数)，寻找一个（连续的）子序列Xi，Xi+1,...Xj,使得其数值之和在所有的连续子序列数值之和中为最大。
一般称这个子序列为最大子序列，例如，在序列（2，-3,1.5，-1,3，-2，-3,3）中，最大的子序列是（1.5，-1,3）它的和是3.5，在一个给定的序列中可能有几个最大子序列。
如果所有的数值为负数，则最大子序列为空（由定义，空的子序列之和为0）。我们希望有一个解决该问题的算法，并且仅对此序列扫描一次。
扩展问题，算法至少还求出一个最大子序列，并且输出。
算法要点：当临时子序列之和小于零时，需要重置临时子序列之和为零，相当于重新起点计算子序列。
如下方法定义于工具类：MaxSubsequenceUtil
public static double FindMaxSubsequence(double[] array, out int startIndex)
{
double GlobeMax = , tmpMax = ;
startIndex = -;
for (int i = array.Length - ; i >= ; i--)
{
tmpMax = tmpMax + array[i];
if (GlobeMax < tmpMax)
{
GlobeMax = tmpMax;
startIndex = i;
}
else if (tmpMax < )
{
tmpMax = ;
}
}
return GlobeMax;
}
方法调用和输出子序列方法：
static void Main(string[] args)
{
double[] dArray = new double[] { , -, 1.5, -, , -, -, };
dArray.ToList<double>().ForEach(d => Console.Write("{0} ", d));
int startIndex;
double max = MaxSubsequenceUtil.FindMaxSubsequence(dArray, out startIndex);
if (max == )
{
Console.WriteLine("No max subsequence exist!");
}
else
{
Console.WriteLine();
Console.WriteLine("The max total is:{0}", max);
Console.WriteLine("The max subsequence is:");
double t = ;
for (int i = startIndex; i < dArray.Length; i++)
{
t += dArray[i];
if (t == max)
{
Console.Write("{0} ", dArray[i]);
break;
}
Console.Write("{0} ", dArray[i]);
}
}
Console.ReadKey();
}
完毕。
下载源码。
作者：Andy Zeng
欢迎任何形式的转载，但请务必注明出处。