Posted on 2013-04-19 15:03
小明 閱讀(1579)
評論(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;
}
}