121. 買賣股票的最佳時機——只允許交易一次 動態(tài)規(guī)劃 || 一次遍歷
給定一個數(shù)組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格憨降。
你只能選擇 某一天 買入這只股票召噩，并選擇在 未來的某一個不同的日子 賣出該股票母赵。設計一個算法來計算你所能獲取的最大利潤逸爵。
返回你可以從這筆交易中獲取的最大利潤具滴。如果你不能獲取任何利潤，返回 0 师倔。
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入构韵，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格疲恢；同時凶朗，你不能在買入前賣出股票。
第二種動態(tài)規(guī)劃
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// 特殊判斷
if (len < 2) {
return 0;
}
int[][] dp = new int[len][2];
// dp[i][0] 下標為 i 這天結束的時候显拳，不持股棚愤，手上擁有的現(xiàn)金數(shù)
// dp[i][1] 下標為 i 這天結束的時候，持股杂数，手上擁有的現(xiàn)金數(shù)
// 初始化：不持股顯然為 0宛畦，持股就需要減去第 1 天（下標為 0）的股價
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 從第 2 天開始遍歷
for (int i = 1; i < len; 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], -prices[i]);
}
return dp[len - 1][0];
}
}
122. 買賣股票的最佳時機 II —— 允許交易無數(shù)次，貪心||動態(tài)規(guī)劃
給定一個數(shù)組 prices 揍移，其中 prices[i] 是一支給定股票第 i 天的價格次和。
設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）那伐。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入踏施，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨后罕邀，在第 4 天（股票價格 = 3）的時候買入畅形，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
貪心算法：
時間復雜度 O(N) ： 只需遍歷一次price诉探；
空間復雜度 O(1)： 變量使用常數(shù)額外空間束亏。
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
int tmp = prices[i] - prices[i - 1];
if (tmp > 0) profit += tmp;
}
return profit;
}
}
動態(tài)規(guī)劃：
dp[i][j] 表示到下標為 i 的這一天，持股狀態(tài)為 j 時阵具，我們手上擁有的最大現(xiàn)金數(shù)碍遍。
確定初始值：起始如果什么都不做，dp[0][0] = 0阳液；如果持有股票怕敬，當前擁有的現(xiàn)金數(shù)是當天股價的相反數(shù)，即 dp[0][1] = -prices[i]帘皿；
時間復雜度：O(N)东跪，這里 NN 表示股價數(shù)組的長度；
空間復雜度：O(N)鹰溜，雖然是二維數(shù)組虽填，但是第二維是常數(shù)，與問題規(guī)模無關曹动。
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// 0：持有現(xiàn)金
// 1：持有股票
// 狀態(tài)轉移：0 → 1 → 0 → 1 → 0 → 1 → 0
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
// 這兩行調(diào)換順序也是可以的
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[len - 1][0];
}
}
123. 買賣股票的最佳時機 III —— 最多買賣2次 動態(tài)規(guī)劃 || 頭尾雙指針
給定一個數(shù)組斋日，它的第i 個元素是一支給定的股票在第 i天的價格。
設計一個算法來計算你所能獲取的最大利潤墓陈。你最多可以完成 **兩筆 **交易恶守。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）第献。
輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出兔港，這筆交易所能獲得利潤 = 3-0 = 3 庸毫。
隨后，在第 7 天（股票價格 = 1）的時候買入衫樊，在第 8 天 （股票價格 = 4）的時候賣出飒赃，這筆交易所能獲得利潤 = 4-1 = 3 。
第一種：動態(tài)規(guī)劃
一天結束時科侈，可能有持股盒揉、可能未持股、可能賣出過1次兑徘、可能賣出過2次刚盈、也可能未賣出過
所以定義狀態(tài)轉移數(shù)組dp[天數(shù)][當前是否持股][賣出的次數(shù)]
具體一天結束時的6種狀態(tài)：
- 未持股，未賣出過股票：說明從未進行過買賣挂脑，利潤為0
dp[i][0][0]=0 - 未持股藕漱，賣出過1次股票：可能是今天賣出，也可能是之前賣的（昨天也未持股且賣出過）
dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1]) - 未持股崭闲，賣出過2次股票:可能是今天賣出肋联，也可能是之前賣的（昨天也未持股且賣出過）
dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2]) - 持股，未賣出過股票：可能是今天買的刁俭，也可能是之前買的（昨天也持股）
dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0]) - 持股橄仍，賣出過1次股票：可能是今天買的，也可能是之前買的（昨天也持股）
dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1]) - 持股牍戚，賣出過2次股票：最多交易2次侮繁，這種情況不存在
dp[i][1][2]=float('-inf')
class Solution:
def maxProfit(self, prices):
if prices==[]:
return 0
length=len(prices)
#結束時的最高利潤=[天數(shù)][是否持有股票][賣出次數(shù)]
dp=[ [[0,0,0],[0,0,0] ] for i in range(0,length) ]
#第一天休息
dp[0][0][0]=0
#第一天買入
dp[0][1][0]=-prices[0]
# 第一天不可能已經(jīng)有賣出
dp[0][0][1] = float('-inf')
dp[0][0][2] = float('-inf')
#第一天不可能已經(jīng)賣出
dp[0][1][1]=float('-inf')
dp[0][1][2]=float('-inf')
for i in range(1,length):
#未持股，未賣出過如孝，說明從未進行過買賣
dp[i][0][0]=0
#未持股宪哩，賣出過1次，可能是今天賣的第晰，可能是之前賣的
dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])
#未持股锁孟，賣出過2次，可能是今天賣的茁瘦，可能是之前賣的
dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])
#持股品抽，未賣出過，可能是今天買的甜熔，可能是之前買的
dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])
#持股圆恤，賣出過1次，可能是今天買的纺非，可能是之前買的
dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])
#持股哑了，賣出過2次，不可能
dp[i][1][2]=float('-inf')
return max(dp[length-1][0][1],dp[length-1][0][2],0)
第二種：頭尾雙指針
以i為分界線烧颖，[0,i]最大 + [i+1,len-1]最大弱左。
從左向右遍歷很簡單的能求出[0,i]最大，從左向右遍歷過程中記錄最小值炕淮，當前值與最小值求差拆火，這個差的最大值就是[0,i]最大
類似的能求出[i+1,len-1]最大，倒著做涂圆。為了便于查找们镜，用數(shù)組maxs[]記錄每個位置右側差的最大值。
實際編碼中我選擇先做[i+1,len-1]最大润歉。在做[0,i]最大過程中模狭，結合maxs[]求出答案。
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int max = 0;
int[] maxs = new int[len + 1];
for (int i = len - 1; i >= 0; i--) {
int price = prices[i];
max = Math.max(max, price);// [i,len-1]位置右側的最大值
maxs[i] = Math.max(maxs[i + 1], max - price);// [i,len-1]最大差值
}
int min = Integer.MAX_VALUE;
max = 0;
for (int i = 0; i < len; i++) {
int price = prices[i];
min = Math.min(min, price);// [0,i]最小值
max = Math.max(max, price - min + maxs[i + 1]);// [0,i]最大值 + [i+1,len-1]最大值
}
return max;
}
}
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
k = Math.min(k, n / 2);
int[][] buy = new int[n][k + 1];
int[][] sell = new int[n][k + 1];
buy[0][0] = -prices[0];
sell[0][0] = 0;
for (int i = 1; i <= k; ++i) {
buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
}
for (int i = 1; i < n; ++i) {
buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
}
}
return Arrays.stream(sell[n - 1]).max().getAsInt();
}
}
