s*****o
发帖数: 1540 | 1 一个经典问题：a vector x of n real numbers. find the max sum found in any
contiguous sub vector。
大家知道，programming pearl的解法是：
maxsofar = 0;
maxendinghere = 0;
for i = [0, n)
maxendinghere = max (maxendinghere + x[i], 0);
maxsofar = max (maxsofar, maxendinghere);
我改动一下，要输出究竟是那个sub vector，请大侠指教是不是正确。
public class MaxSubVector {
static public void findBigestSum(double[] x)
{
double maxsofar = 0;
double maxendinghere = 0;
int maxsofarlow = -1;
int maxsofarhigh = -1;
int maxendinglow = -1;
int maxendinghigh = -1;
for (int i = 0; i < x.length; i ++ )
{
if (maxendinghere + x[i] > 0)
{
maxendinghigh = i;
if (maxendinglow == -1) maxendinglow = i;
maxendinghere = maxendinghere + x[i];
}
else
{
maxendinglow = -1;
maxendinghigh = -1;
maxendinghere = 0;
}
if (maxendinghere > maxsofar)
{
maxsofarlow = maxendinglow;
maxsofarhigh = maxendinghigh;
maxsofar = maxendinghere;
}
}
System.out.println("x = " + x.toString());
System.out.println ("maxsofar = " + maxsofar + " low: "
+ maxsofarlow + " high: " + maxsofarhigh);
if (maxsofarlow != -1 && maxsofarhigh != -1)
{
System.out.print ("[");
double sum2 = 0;
for (int i = maxsofarlow; i <= maxsofarhigh ; i ++)
{
System.out.print (x[i] + " ");
sum2 += x[i];
}
System.out.println ("]");
System.out.println ("Second sum is: " + sum2);
}
else
System.out.println ("Empty sub vector");
}
public static void main(String[] args) {
double x1[] = {-1, 1, -3};
findBigestSum(x1);
double x2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
findBigestSum(x2);
double x3[] = {-1, -1};
findBigestSum(x3);
double x4[] = {-1, 2, -1};
findBigestSum(x4);
}
} |
|
