leetcode_122 买卖股票的最佳时机II

1. 题意

给定一个数组，你可以多次的买入和卖出股票。

你可以在当天买入然后卖出。求最大的获利。

2 题解

还是没有状态这个概念，所以暴力的解法都没有写出来。

主要有两种状态，一是持有股票的最大收益，另一种是不持有股票的最大收益。

当持有股票的时候，你可以卖出股票；而在你没有持有股票的时候，

你可以买入股票。当然你也可以什么也不做。

2.1 暴力

class Solution {public: void getMaxProfit(const vector<int> &prices, int depth, bool hv_stocks,int cur, int &ans) { if (depth == prices.size()) { ans = max(ans, cur); return ; } getMaxProfit( prices, depth + 1, hv_stocks, cur, ans); if ( hv_stocks ) { getMaxProfit( prices, depth + 1, false, cur + prices[depth], ans); } else { getMaxProfit( prices, depth + 1, true, cur - prices[depth], ans); } } int maxProfit(vector<int>& prices) { int ans = 0; getMaxProfit( prices, 0, false, 0, ans); return ans; }};

2.2 动态规划

我们定义$dp[i][0]$表示在遍历到$i$时手上没有股票的最大获利，

而$dp[i][1]$则表示在遍历到$i$时手上有股票的最大获利。

那么状态转移方程为

d p [ i ] [ 0 ] = max ⁡ { d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ i ] } d p [ i ] [ 1 ] = max ⁡ { d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] } dp[i][0] = \\max\\{ dp[i-1][0], dp[i-1][1] + prices[i]\\}\\\\ dp[i][1]=\\max\\{ dp[i-1][1], dp[i-1][0] - prices[i]\\} dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}

同时我们需要注意，初始化$dp[0][0]=0,dp[0][1]=-prices[0]$。

class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; ++i) { dp[i][0] = max( dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = max( dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; }};

可以优化下空间

class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); int dp0 = 0; int dp1 = -prices[0]; for (int i = 1; i < n; ++i) { int tmp = dp0; dp0 = max(dp1 + prices[i], dp0); dp1 = max( dp1, tmp - prices[i]); } return dp0; }};

时间复杂度$O(n)$, 空间复杂度$O(1)$

2.3 贪心

自己感觉最难理解的方法，不过写着写着博客突然想到了怎么理解

这个问题了。

其实最根本的是证明连续上升区间的最优性，最终最优的买入卖出的操作区间集合一定是若干个连续上升区间的并集。

为了方便说明，我们用区间来代替一次买入卖出的操作：

$[l,r]$表示在$l$处买入而在$r$处卖出。

我们说区间$[l,r]$是一个连续上升区间，

也就是说$p[l]<p[l+1]<\cdots <p[r]$

用 S [ l , r ] =p[r]−p[l] S_{[l,r]}=p[r]-p[l] S[l,r]​=p[r]−p[l]来表示一次买入卖出(区间)的收益。

首先我们要有收益，必然有$p[r]>p[l]$。

接下来我们来证明为什么一定要是连续上升区间，我们假设有一个最优的操作区间$[l,r]$，它不满足这个连续上升这个性质；

那么它必然存在一个最小的 r ′ , r ′ <r r\', r\'<r r′,r′<r，

满足 p[ r ′ −1]≥p[r] p[r\'-1] \\ge p[r] p[r′−1]≥p[r]。

此时我们不妨把区间$[l,r]$给分成两个区间 [l, r ′ −1]∪[ r ′ ,r] [l,r\'-1]\\cup[r\',r] [l,r′−1]∪[r′,r]。

此时这两个区间的收益为

S [ l , r ′ − 1 ] ∪ [ r ′ , r ] = ( p [ r ′ − 1 ] − p [ l ] ) + ( p [ r ] − p [ r ′ ] ) = ( p [ r ] − p [ l ] ) + ( p [ r ′ − 1 ] − p [ r ′ ] ) = S [ l , r ] + ( p [ r ′ − 1 ] − p [ r ′ ] ) \\begin{align*} S_{[l,r\'-1]\\cup[r\',r]} &=(p[r\'-1] -p[l]) +(p[r]-p[r\'])\\\\ &=(p[r]-p[l])+(p[r\'-1]-p[r\'])\\\\ &=S_{[l,r]} + (p[r\'-1]-p[r\']) \\end{align*} S[l,r′−1]∪[r′,r]​​=(p[r′−1]−p[l])+(p[r]−p[r′])=(p[r]−p[l])+(p[r′−1]−p[r′])=S[l,r]​+(p[r′−1]−p[r′])​
由于 p[ r ′ −1]≥p[ r ′ ] p[r\'-1]\\ge p[r\'] p[r′−1]≥p[r′]，因此 p[ r ′ −1]−p[ r ′ ]≥0 p[r\'-1]-p[r\'] \\ge 0 p[r′−1]−p[r′]≥0;

S [ l , r ′ − 1 ] ∪ [ r ′ , r ]≥ S [ l , r ] S_{[l,r\'-1]\\cup[r\',r]} \\ge S_{[l,r]} S[l,r′−1]∪[r′,r]​≥S[l,r]​

因此分解为两个区间后的收益是非递减的,有可能会增。

若区间 [ r ′ ,r] [r\',r] [r′,r]依然不是连续上升区间，我们可以继续进行相同的操作使得

分解后收益不减。

这意味着什么呢？

任何一个非连续上升区间都可以分解成若干个连续上升区间使得最终的

收益不减。

S [ l , r ]≤ S [ l , r 0 ] ∪ [ l 1 , r 1 ] ∪ ⋯ [ l k , r ] S_{[l,r]} \\le S_{[l,r_0]\\cup[l_1,r_1]\\cup\\cdots[l_k,r]} S[l,r]​≤S[l,r0​]∪[l1​,r1​]∪⋯[lk​,r]​

至此，我们其实就可以写出代码了。

class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); int ans = 0; int l = 0; for (int i = 1; i < n; ++i) { // 上升连续区间结束了 // 上升区间左端点l, 右端点i - 1 // [l, i - 1] if ( prices[i] <= prices[i-1]) { ans += prices[i - 1] - prices[l]; l = i; } } // 累加最后一个上升连续区间 return ans + (prices[n - 1] - prices[l]); }};

而对于官解中的写法，我更倾向于认为它是一种差分的技巧

S [ l , r ]= ∑ i = l r − 1 S [ i , i + 1 ] S_{[l,r]}=\\sum_{i=l}^{r-1}S_{[i,i+1]} S[l,r]​=i=l∑r−1​S[i,i+1]​

类似于

p [ r ] − p [ l ] = ∑ i = l r − 1p [ i + 1 ] − p [ i ] p[r] -p[l] =\\sum_{i=l}^{r-1}p[i+1] -p[i] p[r]−p[l]=i=l∑r−1​p[i+1]−p[i]

它将一个连续上升区间的收益给划分到多个相邻长度为$2$的上升区间了，

如果这个区间$[i,i+1]$非上升区间了，说明连续区间结束了在之前基础上增加的收益为$0$。

最终的代码当然是如此的简洁，以至于没做出来的我觉得我是个sb，当然

我确实是个sb。

class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); int ans = 0; for (int i = 1; i < n; ++i) { ans += max(0, prices[i] - prices[i - 1]); } return ans; }};

3. 参考

leetcode 122官解