買賣股票的最佳時機 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;
}