题解 | #买卖股票的最好时机(一)#
买卖股票的最好时机(一)
http://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec
解题思路
1.全局贪心
默认全局差值为0
首先找到当前为止股票最低点
当前股票价值大于这个最小值，就可以更新全局差值，取最大值
int maxProfit(vector<int>& prices) {
// write code here
int res = 0;
int minVal = prices[0];
for(int i=1;i<prices.size();i++){
minVal = min(minVal,prices[i]);
res = max(res,prices[i]-minVal);
}
return res;
}
2.动态规划
正常来说dp需要一个数组，这里有两个状态就应该是二维数组。但是每个值只使用一次，所以两个变量就够了。
状态1：当前持有现金价值
状态2：当前持有股票价值
求：最后持有现金价值最大值
初始状态（第一天）：
1.默认持有现金0元，没买股票
2.买股票，就是负债-prices[0]元。（借了这么多钱，买了股票，所以是负数）
状态更新：
1.第n天持有现金价值
情况1：n-1天持有现金，维持现状
情况2: n-1天持有股票，变现（当天股价减去当前持有的股票）
取两者最优（最大值）
2.第n天持有股票价值
情况1：n-1天持有股票，维持现状
情况2: n-1天持有现金，购买股票（借钱买股票，负债-prices[i],注意这里只有一次购买机会，说明之前没有购买过股票）
int maxProfit(vector<int>& prices) {
// write code here
int hasMoney = 0;
int notHasMoney = -prices[0];
for(int i=1;i<prices.size();i++){
hasMoney = max(hasMoney,prices[i]+notHasMoney);
notHasMoney = max(notHasMoney, -prices[i]);
}
return hasMoney;
}
投递金山办公等公司10个岗位
