Leetcode|Leetcode 121. Best Time to Buy and Sell Stock Leetcode121.BestTimetoBuyandSellStoc

【Leetcode|Leetcode 121. Best Time to Buy and Sell Stock】文章作者：Tyan
博客：noahsnail.com|CSDN|
1. Description
文章图片
Best Time to Buy and Sell Stock 2. Solution

Version 1

class Solution { public: int maxProfit(vector& prices) { int max_profit = 0; for(int i = 0; i < prices.size(); i++) { for(int j = i + 1; j < prices.size(); j++) { int profit = prices[j] - prices[i]; if(profit > max_profit) { max_profit = profit; } } } return max_profit; } };

Version 2

class Solution { public: int maxProfit(vector& prices) { int max = 0; int min = INT_MAX; vector current_max(prices.size()); vector current_min(prices.size()); int max_profit = 0; int size = prices.size(); for(int i = 0; i < size; i++) { if(prices[i] < min) { min = prices[i]; } current_min[i] = min; } for(int i = size - 1; i >= 0; i--) { if(prices[i] > max) { max = prices[i]; } current_max[i] = max; } for(int i = 0; i < size; i++) { int profit = current_max[i] - current_min[i]; if(profit > max_profit) { max_profit = profit; } } return max_profit; } };

Version 3

class Solution { public: int maxProfit(vector& prices) { int min = INT_MAX; int max_profit = 0; for(int i = 0; i < prices.size(); i++) { if(prices[i] < min) { min = prices[i]; } else if(prices[i] - min > max_profit) { max_profit = prices[i] - min; } } return max_profit; } };

Reference