股票市场问题（The Stock Market Problem）

Question: Let us suppose we have an array whose i^th element gives the price of a share on the day i.
If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.

要求最佳的买进和卖出时间，也就是利润最大化的点。当买进时的股价小于卖出时的股价就能产生利润。

第一眼看上去，我们也许会想到找到数组的最小点和最大点，但是买必须是在卖之前。

问题等价于：

Find i and j that maximizes Aj – Ai, where i < j.

简单的方法是计算所有的可能性，在比较最大值，需要的时间是O(n²)，也许我们能在O(n)的时间内解决。

要解决这个问题，需要追踪最小值
遍历的同时，更新最小值的索引
比较目前的值与最小值的差值
遍历时更新最大差值

算法实现。

#include<stdio.h>

void getBestTime(int stocks[], int size)

{

    int buy = 0, sell = 0;

    int min = 0;

    int i;

    int maxDiff = 0;

    buy = sell = 0;

    for (i = 0; i < size; i++)

    {

        if (stocks[i] < stocks[min])

            min = i;

        int diff = stocks[i] - stocks[min];

        if (diff > maxDiff)

        {

            buy = min;

            sell = i;

            maxDiff = diff;

        }

    }

    printf("\nThe day to buy is- %d at price %d",buy, stocks[buy]);

    printf("\nThe day to sell is- %d at price %d",sell, stocks[sell]);

}

int main(void)

{

    int stocks[] = {3, 6, 10, 2, 66, 43, 1, 23};

    int buy = 0;

    int sell = 0;

    getBestTime(stocks, 8);

    return 0;

}

巴特西

股票市场问题（The Stock Market Problem）

最新文章

热门文章