Posted on 2013-04-19 21:50
小明 閱讀(1857)
評(píng)論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：為了得到最大收益，必須在所有上升的曲線段的開始點(diǎn)買入，在最高點(diǎn)賣出。而在下降階段不出手。
實(shí)現(xiàn)代碼如下：
public class Solution {
public int maxProfit(
int[] prices) {
int len = prices.length;
if(len<2){
return 0;
}
int min=0;
int result = 0;
boolean inBuy =
false;
for(
int i=0;i<len-1;++i){
int p = prices[i];
int q = prices[i+1];
if(!inBuy){
if(q>p){
inBuy =
true;
min=p ;
}
}
else{
if(q<p){
result += (p-min);
inBuy =
false;
}
}
}
if(inBuy){
result += ((prices[len-1])-min);
}
return result;
}
}