C语言买卖股票问题

　　遇到个简单的算法题，没有当场解出来，以后可以写伪代码表达思路。

　　数组中保存每天的股票价值，求买入卖出的时间和最大利润，比较好的解法如下：

伪代码：

begin

start day = 0; end day = 0; max value = 0;

for day 1 to N;

　　value = next day's value - today's value;

if value > 0

　　get max value and day;

else if value < 0

　　today = next day;

end

实际编码：

#define N 10
int value[N] = { 5, 8, 3, 9, 10, 4, 5, 14, 2, 7 };

void GetMaxValue(int * start, int * end, int * max)
{
    int curr_day = 0, next_day = 0, tmp_max = 0;

    for (next_day = 1; next_day < N && curr_day < N; next_day++)
    {
        tmp_max = value[next_day] - value[curr_day];

        if (tmp_max > *max)//保存比较大的利润和买卖日期
        {
            *max = tmp_max;
            *start = curr_day;
            *end = next_day;
        }
        else if (tmp_max < 0)//后一天股票值比今天低，可能存在更高利润，作为新起点计算
        {
            curr_day = next_day;
        }
    }

    printf("start_day:%d , end_day:%d ,max_value:%d 
", *start, *end, *max);
}

思路：

       自己的第一印象是两个循环，先求出每天买入可得的最大利润，然后再循环一次获取最大的利润，这种是复杂度最高的，里面存在重复计算，当时没有想到优化的办法。后来仔细想了想，用一个循环完全可以解决，思路如下：

　　从第一天开始，第二天的股票值如果比今天高，那就保存买卖日期和利润，这样继续下去肯定能得到今天买入的最大利润及卖出日期。并且，后面比今天价格高的日期根本不需要计算，因为利润肯定没今天高。

也就是说只需要这一个循环，后面价格高的统统排除掉了。

　　如果后面某天价格比今天低呢，那就可能存在更大的利润了，所以现在当前计算的日期不需要继续计算，用低价日作为新的起点。因为假如后面有高价日，那今日卖出的利润也没低价日卖出的高。

　　然后就是重复计算新低价日期能获得的最佳结果，跟旧结果比，取最优值。