题目列表
- 121 Best Time to Buy and Sell Stock
- 122 Best Time to Buy and Sell Stock II
- 123 Best Time to Buy and Sell Stock III
- 188 Best Time to Buy and Sell Stock IV
- 309 Best Time to Buy and Sell Stock with Cooldown
- 714 Best Time to Buy and Sell Stock with Transaction Fee
121.Best Time to Buy and Sell Stock
题解
贪心
越小越有优势,每次读取维持买入最小值即可
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int goal = 0;
int n = prices.size();
for( int i = 1; i < n; ++ i )
{
goal = max( goal, prices[ i ] - prices[ 0 ] );
prices[ 0 ] = min( prices[ 0 ], prices[ i ] );
}
return goal;
}
};
122.Best Time to Buy and Sell Stock II
题解
贪心
因为可以无限次选择，那么选择每次选择相邻两个的差值为正的两个股票
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sum = 0;
int n = prices.size();
for( int i = 1; i < n; ++ i ) sum += ( max( prices[ i ] - prices[ i - 1 ], 0 ) );
return sum;
}
};
123.Best Time to Buy and Sell Stock III
题解
dp
dp[ i ][ k ] 表示前i个股票在在最多买卖k次的情况下的最大收益
那么状态方程不难想到
dp[ i ][ k ] = max( dp[ i ][ k - 1 ], prices[ i ] - prices[ j ] + dp[ j - 1 ][ k - 1 ] ) ( 0 <= j <= i )
若不进行优化,则时间复杂度为 O( kn^2 )
观察上面转移方程: dp[ j - 1 ][ k - 1 ] - prices[ j ] 与i无关,那么在i的循环过程中,维护dp[ j - 1 ][ k - 1 ] - prices[ j ]最大,就可以省去j的那部分循环,时间复杂度为O( kn )
代码
//O(kn^2)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if( !n ) return 0;
vector< vector< int > > dp( n, vector< int >( 3 ) );
for( int k = 1; k <= 2; ++ k )
for( int i = 1; i < n; ++ i )
{
int pay = - prices[ 0 ];
for( int j = 1; j <= i; ++ j ) pay = max( pay, dp[ j - 1 ][ k - 1 ] - prices[ j ] );
dp[ i ][ k ] = max( dp[ i - 1 ][ k ], prices[ i ] + pay );
}
return dp[ n - 1 ][ 2 ];
}
};
//O(kn)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if( !n ) return 0;
vector< vector< int > > dp( n, vector< int >( 3 ) );
for( int k = 1; k <= 2; ++ k )
{
int pay = - prices[ 0 ];
for( int i = 1; i < n; ++ i )
{
pay = max( pay, dp[ i - 1 ][ k - 1 ] - prices[ i ] );
dp[ i ][ k ] = max( dp[ i - 1 ][ k ], prices[ i ] + pay );
}
}
return dp[ n - 1 ][ 2 ];
}
};
188. Best Time to Buy and Sell Stock IV
题解
dp
解法同123.Best Time to Buy and Sell Stock III
注意当 k > prices.size()/2 时,就变成了 122.Best Time to Buy and Sell Stock II
代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if( !n ) return 0;
if( k > n / 2 ) return get_val( prices );
vector< vector< int > > dp( n, vector< int >( k + 1 ) );
for( int num = 1; num <= k; ++ num )
{
int pay = - prices[ 0 ];
for( int i = 1; i < n; ++ i )
{
pay = max( pay, dp[ i - 1 ][ num - 1 ] - prices[ i ] );
dp[ i ][ num ] = max( dp[ i - 1 ][ num ], prices[ i ] + pay );
}
}
return dp[ n - 1 ][ k ];
}
int get_val( vector<int>& prices )
{
int sum = 0;
int tmp = -1;
for( auto price: prices )
{
if( tmp == -1 ) tmp = price;
sum += ( max( price - tmp, 0 ) );
tmp = price;
}
return sum;
}
};
309. Best Time to Buy and Sell Stock with Cooldown
题解
dp
首先用一维分析dp[ i ] 表示前i个股票的最大获益,不难得出状态转移方程
dp[ i ] = max( dp[ i ], prices[ i ] - prices[ j ] + dp[ j - 1 ] )
这样出现了问题,无法判断这个dp[ j - 1 ]是否用了prices[ j - 1 ]
所以添加一维
dp[ i ][ 0 ] 表示前i个股票没有使用prices[ i ]的最大获益
dp[ i ][ 1 ] 表示前i个股票使用了prices[ i ]的最大获益
不难得出状态转移方程
dp[ i ][ 1 ] = max( dp[ i ][ 1 ], dp[ j - 1 ][ 0 ] + prices[ i ] - prices[ j ] ) (0 <= j <= i)
dp[ i ][ 0 ] = max( dp[ j ][ 0 ], dp[ j ][ 1 ] ) (0 <= j <= i - 1)
时间复杂度为 o( n^2 )
分析
dp[ j - 1 ] - prices[ j ] 和 max( dp[ j ][ 0 ], dp[ j ][ 1 ] ) 与 i 无关，可以随着i的递增中维护最大值.故时间复杂度为 o( n )
代码
// o( n^2 )
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if( !n ) return 0;
vector< vector< int > > dp( n, vector< int >( 2 ) );
for( int i = 1; i < n; ++ i )
{
for( int j = 0; j <= i; ++ j )
{
if( j == 0) dp[ i ][ 1 ] = max( dp[ i ][ 1 ], prices[ i ] - prices[ j ] );
else dp[ i ][ 1 ] = max( dp[ i ][ 1 ], dp[ j - 1 ][ 0 ] + prices[ i ] - prices[ j ] );
if( j != i ) dp[ i ][ 0 ] = max( dp[ j ][ 0 ], dp[ j ][ 1 ] );
}
}
return max( dp[ n - 1 ][ 0 ], dp[ n - 1 ][ 1 ] );
}
};
// o( n )
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if( !n ) return 0;
vector< vector< int > > dp( n, vector< int >( 2 ) );
int pay = - prices[ 0 ];
for( int i = 1; i < n; ++ i )
{
dp[ i ][ 1 ] = max( dp[ i ][ 1 ], prices[ i ] + pay );
pay = max( pay, dp[ i - 1 ][ 0 ] - prices[ i ] );
dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ], dp[ i - 1 ][ 1 ] );
}
return max( dp[ n - 1 ][ 0 ], dp[ n - 1 ][ 1 ] );
}
};
714. Best Time to Buy and Sell Stock with Transaction Fee
题解
dp
dp[ i ]表示前i个股票所得的最大收益. 状态转移方程为
dp[ i ] = max( dp[ i - 1 ], dp[ j ] + prices[ i ] - prices[ j ] - fee );
时间复杂度o(n^2)
分析
dp[ j ] - prices[ j ] 与i无关，可以随着i的增加维护最大值 省去j的那重循环
时间复杂度o(n)
代码
//o(n^2)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
if( !n ) return 0;
vector< int > dp( n );
for( int i = 1; i < n; ++ i )
{
dp[ i ] = dp[ i - 1 ];
for( int j = 0; j < i; ++ j )
dp[ i ] = max( dp[ i ], dp[ j ] + prices[ i ] - prices[ j ] - fee );
}
return dp[ n - 1 ];
}
};
//o(n)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
if( !n ) return 0;
vector< int > dp( n );
int pay = -prices[ 0 ];
for( int i = 1; i < n; ++ i )
{
dp[ i ] = dp[ i - 1 ];
dp[ i ] = max( dp[ i ], prices[ i ] + pay - fee );
pay = max( pay, dp[ i ] - prices[ i ] );
}
return dp[ n - 1 ];
}
};
