使股份利润最大化（最大子数组）

Question

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

然而，我编写了一个算法，它将花费0(n)个时间，并找到最大利润。这是在0(n)对0(nlogn)的最大子数组问题。但我知道作者不会错的。我哪里出错了？我的算法正确吗？

#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;
}

Answer 1

在这里，你正在寻找最大的利益，你可以通过买卖一次股票（一次是重要的）。

你的算法假设最好的利润将产生于股票的最低执行价格。这是错误的：例如，A[]={10,23,6,12,4,1,0,3}，程序输出3，而最大好处显然是13（关于Coliru的证明）

最佳效益的一个特征是计算股票固定的增量数组（您引用的A[]={-2,-5,6,-2,-3,1,5,-6}数组），然后得到最大子数组。在我的示例中，我们得到f[]={13,-17,6,-8,-3,-1,3}，最大子数组是{13}。最终，所需利润为最大子数组之和。

#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;
}

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