買賣股票的最佳時機

題目描述：

給定一個數組?prices?，它的第?i?個元素?prices[i]?表示一支給定股票第?i?天的價格。

你只能選擇?某一天?買入這只股票，并選擇在?未來的某一個不同的日子?賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回?0?。

輸入輸出示例：

輸入：[7,1,5,3,6,4]

輸出：5

解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。 注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

解題方案：

方式一：暴力求解（不推薦）

算法思路：最低買入，最高賣出 我們需要找出給定數組中兩個數字之間的最大差值（即，最大利潤）。此外，第二個數字（賣出價格）必須大于第一個數字（買入價格）。

形式上，對于每組 i 和 j（其中 j>i）我們需要找出 max(prices[j]?prices[i])。

實現代碼

public class Solution {public int maxProfit(int[] prices) {int maxprofit = 0;//i指向買入時的價格for (int i = 0; i < prices.length - 1; i++) {//j指向賣出時的價格for (int j = i + 1; j < prices.length; j++) {//求出利潤int profit = prices[j] - prices[i];if (profit > maxprofit) {maxprofit = profit;}}}return maxprofit;}
}

復雜度分析

時間復雜度：O(n2)。二重循環，循環運行?2n(n?1)??次。

空間復雜度：O(1)。只使用了常數個變量。

方法二：一次遍歷

算法思想：假設給定的數組為：[7, 1, 5, 3, 6, 4]

如果我們在圖表上繪制給定數組中的數字，我們將會得到：

如果自己購買股票，每天肯定會想：如果股票在歷史最低點賣出就好了

因此，用變量記錄歷史最低點，同時計算自己的股票在第i天賣出能夠獲得的利潤，每天都不斷地更新這兩個變量，從而可以在遍歷一次數組的情況下，就可以獲得最大利潤

class Solution {public int maxProfit(int[] prices) {//初始化變量,最大利潤ans為0,默認第一天prices[0]為股票最低價格買入int ans=0,minPrice=prices[0];//遍歷傳入的數組prices中的每個元素，并把當前元素賦值給變量pfor(int p:prices){//更新最大利潤;計算當前賣出去價格p減去之前的最低買入價格minPrice的利潤;與之前獲取的利潤ans比較，獲取最大利潤ans=Math.max(ans,p-minPrice);//更新最低買入價格,采用當前價格p和之前的最低價minPrice中較小的一個minPrice=Math.min(minPrice,p);}return ans;//返回最大利潤
}
}

買賣股票的最佳時機 進階版

題目描述

給你一個整數數組?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。最大總利潤為 4 + 3 = 7 。

解題方案

方式一：動態規劃

算法思想：

定義狀態

dp[i][0] 表示第 i 天交易完后手里沒有股票的最大利潤，

dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利潤（i 從 0 開始）。

如果這一天交易完后手里沒有股票，考慮 dp[i][0] 的值會有兩種情況：

• 前一天已經沒有股票，即 dp[i?1][0]，
• 前一天結束的時候手里持有一支股票，即 dp[i?1][1]，這時候我們要將其賣出，并獲得 prices[i] 的收益。

如果這一天交易完后手里有股票，考慮 dp[i][1] 的值會有兩種情況：

• 前一天已經持有一支股票，即 dp[i?1][1]
• 前一天結束時還沒有股票，即 dp[i?1][0]，這時候我們要將其買入，并減少 prices[i] 的收益。

初始條件可以由計算得到 dp[0][0]=0，dp[0][1]=?prices[0]。

由于全部交易結束后，持有股票的收益一定低于不持有股票的收益，因此這時候 dp[n?1][0] 的收益必然是大于 dp[n?1][1] 的，最后的答案即為 dp[n?1][0]。

每一天的狀態只與前一天的狀態有關，而與更早的狀態都無關，因此我們不必存儲這些無關的狀態，只需要將 dp[i?1][0] 和 dp[i?1][1] 存放在兩個變量中，通過它們計算出 dp[i][0] 和 dp[i][1] 并存回對應的變量，以便于第 i+1 天的狀態轉移即可。

實現代碼

class Solution {public int maxProfit(int[] prices) {int n = prices.length;//初始化int dp0 = 0, dp1 = -prices[0];for (int i = 1; i < n; ++i) {//對于每一天，都計算出持有股票的收益和未持有股票的收益，不斷地進行迭代int newDp0 = Math.max(dp0, dp1 + prices[i]);int newDp1 = Math.max(dp1, dp0 - prices[i]);dp0 = newDp0;dp1 = newDp1;}return dp0;}
}

方法二：貪心

算法思想：由于股票的購買沒有限制，因此整個問題等價于尋找?x?個不相交的區間?(li,ri?]?使得如下的等式最大化

其中?li??表示在第?li??天買入，ri??表示在第?ri??天賣出。

?

如圖所示，如果第i天的價格高于第i-1天的價格，則將利潤加入到總利潤當中

需要說明的是，貪心算法只能用于計算最大利潤，計算的過程并不是實際的交易過程。

實現代碼：

class Solution {public int maxProfit(int[] prices) {int ans = 0;int n = prices.length;for (int i = 1; i < n; ++i) {ans += Math.max(0, prices[i] - prices[i - 1]);}return ans;}
}

復雜度分析

時間復雜度：O(n)，其中?n?為數組的長度。我們只需要遍歷一次數組即可。

空間復雜度：O(1)。只需要常數空間存放若干變量。

歡迎大家點贊，評論加收藏

?