白菜连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该白菜第i天的"/>
已知一支白菜连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该白菜第i天的
风口的猪
已知一支白菜连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该白菜第i天的股价。 假设你一开始没有白菜,但有至多两次买入1棵而后卖出1棵的机会,并且买入前一定要先保证手上没有白菜。若两次交易机会都放弃,收益为0。 设计算法,计算你能获得的最大收益。 输入数值范围:2<=n<=100,0<=prices[i]<=100
输入例子:
3,8,5,1,7,8
输出例子:
12
public class Solution {/*** 计算你能获得的最大收益* * @param prices Prices[i]即第i天的股价* @return 整型*/public int calculateMax(int[] prices) {if(prices==null || prices.length==0 || prices.length<2 || prices.length>100){return 0;}int len = prices.length;int[] dpl = new int[len];dpl[0] = 0;int minI = 0; for(int i=1; i<len; i++){ //从左到右扫描一遍填充dpl数组if(prices[i]>prices[i-1]){dpl[i] = Math.max(prices[i]-prices[minI],dpl[i-1]);} else{dpl[i] = dpl[i-1];if(prices[i]<prices[minI])minI = i;}}int[] dpr = new int[len]; dpr[len-1] = 0;int maxI = len-1;for(int i=len-2; i>=0; i--){//从右到左扫描一遍填充dpr数组if(prices[i]<prices[i+1]){dpr[i] = Math.max(prices[maxI]-prices[i], dpr[i+1]);} else{dpr[i] = dpr[i+1];if(prices[i]>prices[maxI]){maxI = i;}}}int res = 0;for(int i=0; i<len; i++){ //比较得出最大值res = Math.max(dpl[i]+dpr[i], res);}return res;}}
更多推荐
已知一支白菜连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该白菜第i天的
发布评论