轩辕互动面试题目-----股市最大收益（转）

使用一个整数数组保存每天的股票价格，如A={20034,20015,20064,20088,20078,20099,21090},表示200.34$,200.15$等，最大收益是21090-20015.

给出这样一个数组A，计算股市的最大收益，请考虑该数组中可能有几百兆数据。

我回家之后终于明白了最大收益的含义：第i天的MaxProfit等于第i天的价格减去MIN（0--i-1）。

下面是最开始的代码

int maxprofit(int A[], int n)   
{   
    int     minBefore;   
    int     maxProfit;   
    int     i;   
    assert(NULL != A);   
    if(0 == n || 1 == n) return 0;   
    maxProfit = 0;   
    minBefore = A[0];   
    for(i = 1; i < n; i++) {   
        if(maxProfit < (A[i] - minBefore)) {   
            maxProfit = A[i] - minBefore;   
        }   
        minBefore = (minBefore < A[i]) ? minBefore : A[i];   
    }   
    if(maxProfit > 0) return maxProfit;   
    return -1;   

看过评论，想了下，还是没有完全理解最大受益，看下面这版

/*******************************************************************************  
 *  \file    minbefore.c  
 *  \brief     
 *  \date    10/09/2009 04:06:20 PM  
 *  \author  Magic(CHD-ZYP), [e-mail]  
 *  \company SECRET  
 ******************************************************************************/  
  
#include    <stdio.h>   
#include    <stdlib.h>   
#include    <assert.h>   
int maxprofit(int A[], int len,  int day)   
{   
    int     minBefore;   
    int     i;   
    assert(NULL != A && day > 0 && len >= day);   
    if(1 == day) return 0;    
    minBefore = A[0];   
    for(i = 1; i < day - 1; i++) {   
        minBefore = (minBefore > A[i]) ? A[i] : minBefore;   
    }   
    return ((minBefore < A[day - 1]) ? (A[day - 1] - minBefore) : 0);   
}   
  
int main ( int argc, char *argv[] )   
{   
    int     a[] = {20034,20015,20064,20088,20078,20099,21090};   
    int     i;   
    for(i = 0; i < sizeof(a) / sizeof(int); i++) {   
        printf("%d day maxprofit is %d\n", i + 1, maxprofit(a, sizeof(a) / sizeof(int), i + 1));   
    }   
    return EXIT_SUCCESS;   
}  

评论

2 楼 will-vip 2010-04-19  

我想可以分段处理，每次读入多少一段，然后得出该段的最大利益值，记录该段的最大值，应该就可以了。同时处理多段应该也不错。

1 楼 wen.owen 2010-01-20  

楼主想说明什么？不就是数组中最后一个数减去数据中最小的一个数即为最大收益吗？我觉得出题者的意图是在后面附加的条件，假设有一天有几百M的数据，怎么计算，不可能全都放到一个数组中吧？