目次
まずは総当たりで実装してみる
とりあえず動くコードを書いてみます。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for (size_t buy = 0; buy < prices.size()-1; buy++) {
for (size_t sell = buy+1; sell < prices.size(); sell++) {
profit = std::max(profit, prices[sell]-prices[buy]);
}
}
return profit;
}
};時間計算量はO(n^2), 空間計算量はO(1)です。
線形時間(O(n))にしたい
時間計算量をO(n^2)からO(n)にします。
最安値を覚えておくことがポイントです。
class Solution {
public:
int maxProfit(const vector<int>& prices) {
int min = prices.front();
int profit = 0;
for (int price : prices) {
min = std::min(min, price);
profit = std::max(profit, price-min);
}
return profit;
}
};おまけ
私が手動で探すときのイメージを実装してみました。
- 最初、最安値・最高値を探し、最高値が最安値より後ろであればその分の利益を返す。
- 上記の条件に合致しなかった場合、(以後indexの話)「先頭 ~ 最高値」、「最高値+1 ~ 最安値-1」、「最安値 ~ 後尾」の3つの中で最大の利益を探す。
class Solution {
public:
int maxProfit(const vector<int>& prices) {
if (prices.size() <= 1) {
return 0;
}
auto min = std::min_element(prices.cbegin(), prices.cend());
auto max = std::max_element(prices.cbegin(), prices.cend());
if (*min == *max) {
return 0;
}
size_t min_distance = std::distance(prices.cbegin(), min);
size_t max_distance = std::distance(prices.cbegin(), max);
if (min_distance < max_distance) {
return *max - *min;
}
if (min+1 == prices.cend() && max == prices.cbegin()) {
return maxProfit(std::vector<int>(prices.cbegin()+1, prices.cend()-1));
}
auto max_after_min = std::max_element(prices.cbegin()+min_distance, prices.cend());
auto min_befor_max = std::min_element(prices.cbegin(), prices.cbegin()+max_distance+1);
return std::max(std::max(*max-*min_befor_max, *max_after_min-*min),
maxProfit(std::vector<int>(prices.cbegin()+max_distance+1, prices.cbegin()+min_distance)));
}
};以上です！