买卖股票的最佳时机 II
题目要求
给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例
-
示例1
输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3
天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第
5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
-
示例2
输入: prices = [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解法
- 解法一(动态规划)
public static int maxProfit(int[] prices) {
if(prices==null||prices.length<2) {
return 0;
}
int length=prices.length;
//dp[i][1]:第i+1天手里无股票 = (前天手里无股票的利润,前天手里有股票+今天卖出股票的价格)的较大值
//dp[i][0]:第i+1天手里有股票 = (前天手里有股票的利润,前天手里无股票-今天买进股票的价格)的较大值
int [][]dp=new int[length][2];
//手里有股票的利润
dp[0][1]=-prices[0];
//手里无股票的利润
dp[0][0]=0;
for(int i=1;i<length;i++) {
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
//手里没有股票,利润最大
return dp[length-1][0];
}
解法二(贪心)
思路:
我们可以想到当股票赚钱,一定是卖的时候价格>买的时候的价格,所以我们可以算出一直涨的时候的最大值-最小值,累加和就是所求的值。而当出现股票下跌时,我们不需要关心。
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int total = 0, index = 0, length = prices.length;
while (index < length) {
//如果股票下跌就一直找,直到找到股票开始上涨为止
while (index < length - 1 && prices[index] >= prices[index + 1])
index++;
//股票上涨开始的值,也就是这段时间上涨的最小值
int min = prices[index];
//一直找到股票上涨的最大值为止
while (index < length - 1 && prices[index] <= prices[index + 1])
index++;
//计算这段上涨时间的差值,然后累加
total += prices[index] - min;
index++;
}
return total;
}
解法三
核心:找出相邻的两天的增长的,
public int maxProfit(int[] prices) {
int max = 0;
for (int i = 1; i < prices.length; i++) {
//今天>昨天,说明股票是上涨的,将正利息累加
if (prices[i] > prices[i - 1]) {
max = max + (prices[i] - prices[i - 1]);
}
}
return max;
}