题目:
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可获得的最大利润是多少?
示例:
一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果
我们能在价格为5的时候买入并在价格为16时卖出,则能获得最大的利润为11.
解法:
/**
* 某天能获得最大利润取当天价格减去以前最小价格的值和
* 当天之前能获得的最大利润两者中的最大值。
* 比如{7,1,5,3,6,8},dp[5]=Max(8-1,6)=7
* @param prices
* @return
*/
public static int maxProfit(int[] prices){
if (prices == null||prices.length==0) {
return 0;
}
int length = prices.length;
if (length==1){
return 0;
}
int[] dp=new int[length];//dp[i]表示到第i天的最大利润
int min=prices[0];//记录当天之前的最小值
dp[0]=0;
for (int i = 1; i <length ; i++) {
dp[i]=Math.max(dp[i-1],prices[i]-min);
if (prices[i]<min){
min=prices[i];
}
}
return dp[length-1];
}
网友评论