题解 | #买卖股票的最好时机#
买卖股票的最好时机
http://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec
class Solution {
public:
/**
*
* @param prices int整型vector
* @return int整型
*/
/*动态规划
int maxProfit(vector<int>& prices) {
// write code here
int n = prices.size();
vector<int> dp(n);
dp[0] = 0;
int maxv = dp[0];
for (int i = 1; i < n; i ++) {
if (dp[i - 1] > 0) {
dp[i] = dp[i - 1] + (prices[i] - prices[i - 1]);
}
else {
dp[i] = prices[i] - prices[i - 1];
}
maxv = max(maxv, dp[i]);
}
return maxv;
}
*/
//贪心算法
int maxProfit(vector<int>& prices) {
int minv = prices[0];
int profit = 0;
for (int i = 0; i < prices.size(); i ++) {
minv = min(minv, prices[i]);
profit = max(profit, prices[i] - minv);
}
return profit;
}
};