首页 文章

最大化股票利润（最大子阵列）

提问于
浏览 次
0

我正在阅读“算法导论” . 在最大的子阵列问题（第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

algorithm

1 回答

  • 2

    在这里，您正在寻找通过买卖股票一次可以获得的最大利益（曾经很重要） .

    您的算法假设最佳利润将来自股票的最低执行价格 . This is wrong ：例如 A[] = {10,23,6,12,4,1,0,3} ，你的程序输出3，而最大的好处显然是13（证明Coliru）

    最佳效益的特征是计算库存定价的delta数组（您引用的 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;
}

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

    回复于

相关问题