买卖股票的最佳时机——数组、动态规划
目录
题目
本题目来自：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
121. 买卖股票的最佳时机
难度简单2177收藏分享切换为英文接收动态反馈
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
题解
暴力法
超时，不必多说。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max = 0;
for( int i=0;i<prices.size()-2;i++){
for(int j=i+1;j<prices.size()-1;j++){
if(prices[j]-prices[i]>max){
max = prices[j]-prices[i];
}
}
}
return max;
}
};
时间复杂度O(n^2)，空间复杂度O(1)
动态规划
假设我们有穿越时空的能力，再假设我们决定在第i天卖出，那么只要知道在0~i天的最低价，再穿越回去购买股票，就能获得最大收益了。
创建一个dp[i]数组，表示在第i天卖出时的最低价。
然后再根据dp[i]数组，找到收益最大的那一天，即确定prices[i]-dp[i]的最大值。
//dp[i]表示截止到i，价格的最低点是多少 dp[i]=min(dp[i-1],nums[i])
int max = 0;
int[] dp = new int[prices.length];
dp[0] = prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i] = (dp[i - 1] < prices[i]) ? dp[i - 1] : prices[i];
max = (prices[i] - dp[i]) > max ? prices[i] - dp[i] : max;
}
return max;
// 参考https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/930057
这个代码还可以进一步优化，因为我们只关注最大值，所以可以不用把所有数据都存到数组里。维护一个minprice和maxprofit变量即可。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int inf = 1e9;
int minprice = inf, maxprofit = 0;
for(int price:prices){
minprice = min(price, minprice);
maxprofit = max(maxprofit, price-minprice);
}
return maxprofit;
}
};
这样只要遍历一遍数组，时间复杂度O(n)，空间复杂度O(1)。
其他小问题
1e9表示1*10^9。在算法题中常用来赋一个非常大的值。为什么不用1e10呢？因为int类型中1e10会溢出。
详情可以参考：http://t.csdn.cn/rItZr