algorithm - 最大化股票的利润(最大子数组)

Question

我正在阅读“算法导论”。在最大子数组问题(第 4 章)中，作者声称不能仅通过找到数组的最大值和最小值来计算买卖股票的最大利润。作者通过计算需要 0(n^2) 时间的买卖日期的所有可能组合来谈到诸如蛮力之类的替代方案。另一种选择是在价格数组中找到每日变化的最大子数组。

但是，我编写了一个需要 0(n) 时间并找到最大利润的算法。这是 0(n) vs 0(n log n) 的最大子数组问题。但我知道作者不会错。我哪里错了？我的算法正确吗？

#include <stdio.h>
#include <limits.h>

int main(void) 
{
    int A[8]={10,8,3,9,7,4,5,10,4};
    int i,max,min,currmax,prevmax,n=8;

    max=INT_MIN;
    min=INT_MAX;
    for(i=0;i<n;i++)
    {
        if(A[i]>max)
        {
            max=A[i];
            prevmax=currmax;
            currmax=max-min;
        }
        if(A[i]<min)
        {
            min=A[i];
            max=INT_MIN;
        }

    }

    if(prevmax>currmax)
        printf("%d",prevmax);
    else
        printf("%d",currmax);

    return 0;
}

---

正如 GeeksForGeeks ( http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/ ) 中给出的，股票价格每日变化的输入是 A[ ]={-2, -5, 6, -2, -3, 1, 5, -6}。我将基本价格设为 10，并将算法运行为 A[ ]={10,8,3,9,7,4,5,10,4};

输入:10,8,3,9,7,4,5,10,4

输出:7

Answer 1

在这里，您正在寻找通过买卖股票一次可以获得的最大 yield (一次很重要)。

您的算法假设最佳利润来自股票的最低行使价。 这是错误的:例如对于 A[] = {10,23,6,12,4,1,0,3}，您的程序输出 3 而最大值 yield 显然是 13(关于 Coliru 的证明)

最佳 yield 的特征是计算股票定盘价的增量数组(A[ ]={-2, -5, 6, -2, -3, 1, 5, -6} 你引用的数组)，然后得到最大的子数组。在我的示例中，我们得到 F[] = {13, -17, 6, -8, -3, -1, 3} 并且最大子数组是 {13} .最终要求的利润是最大子数组的和。

查看它的另一种方法是迭代地保持数组 A[0..i-1] 的最小值(i 范围从 1 到 n -1).在指数i(即在时间i卖出)，最佳利润是A[i] - min(A[0..i-1] )，如果差异为负则为 0。您现在必须跟踪这些差异的最大值。最后，所述最大值是期望的结果。

这基本上就是您的算法所做的。可以找到更清晰的实现running here

#include <stdio.h>
#include <limits.h>

int main(void) 
{
    int A[8]={10,23,6,12,4,1,0,3};
    int i,min_i, profit_i, best_profit=0,n=8;

    min_i=A[0];
    for(i=1;i<n;i++)
    {
        profit_i = A[i] - min_i;
        best_profit = (profit_i > best_profit) ? profit_i : best_profit;

        if(A[i]<min_i)
        {
            min_i=A[i];
        }

    }

    printf("Best profit: %d", best_profit);
    return 0;
}

有不必要的局部变量，但我发现它们使逻辑更容易理解。