Posted on 2013-04-19 15:03
小明 阅读(1572)
评论(0) 编辑 收藏 所属分类:
数据结构和算法
分析：
先看一个股票的变化曲线
记住卖总是在买之后。
遍历数组，如果发现比当前的最小值还要小，就重新购买
如果发现比当前最大值还要大，就试着卖出。
代码如下：O(n)复杂度
public class Solution {
public int maxProfit(
int[] prices) {
int len = prices.length;
if(len<2){
return 0;
}
int min,max;
int result = 0;
min = max = prices[0];
for(
int i=1;i<len;++i){
int p = prices[i];
if(min>p){
//reset
max = min = p;
}
else if(max<p){
max = p;
int diff = max-min;
if(result<diff){
result = diff;
}
}
}
return result;
}
}