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];
}
};