Best Time to Buy and Sell Stock easy題
我自己會暴力解
然後當然不會過
可悲
然後學一下DP怎麼寫
題外話
要怎麼runtime跟memory都beat90%啊
要壓那麼低是有甚麼特殊解法嗎
還是單純我太爛
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int n = prices.size();
if(n<1) return 0;
vector<int> min_price(n);
vector<int> max_profit(n);
min_price[0]=prices[0];
max_profit[0]=0;
for(int i=1;i<n;i++){
min_price[i]=min(min_price[i-1], prices[i]);
max_profit[i]=max(max_profit[i-1], prices[i]-min_price[i-1]);
}
return max_profit[n-1];
}
};