leetcodeノート:Best Time to Buy and Sell Stock III
一.タイトルの説明
Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
二.テーマ分析
前の2つの問題に比べて、この問題は株の取引回数を制限し、最大2回しか取引できない.
動的計画を使用して完了することができ、まず、シーケンス
第2のステップは逆走査であり、サブシーケンス
最後のステップは、
三.サンプルコード
四.小結
前の2つの問題に比べて、この問題は少し難易度が高く、この問題に関連する問題はいくつかあります.次の更新...
Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
二.テーマ分析
前の2つの問題に比べて、この問題は株の取引回数を制限し、最大2回しか取引できない.
動的計画を使用して完了することができ、まず、シーケンス
[0, …, i]
の最大利益profit
を計算し、1つの配列f1
で保存し、このステップの時間的複雑さはO(n)
である.第2のステップは逆走査であり、サブシーケンス
[i, …, n - 1]
の最大利益profit
を計算し、同様に1つの配列f2
で保存し、このステップの時間的複雑さもO(n)
である.最後のステップは、
f1 + f2
に対して、最大値を見つければよい.三.サンプルコード
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices)
{
int size = prices.size();
if (size <= 1) return 0;
vector<int> f1(size);
vector<int> f2(size);
int minV = prices[0];
for (int i = 1; i < size; ++i)
{
minV = std::min(minV, prices[i]);
f1[i] = std::max(f1[i - 1], prices[i] - minV);
}
int maxV = prices[size - 1];
f2[size - 1] = 0;
for (int i = size-2; i >= 0; --i)
{
maxV = std::max(maxV, prices[i]);
f2[i] = std::max(f2[i + 1], maxV - prices[i]);
}
int sum = 0;
for (int i = 0; i < size; ++i)
sum = std::max(sum, f1[i] + f2[i]);
return sum;
}
};
四.小結
前の2つの問題に比べて、この問題は少し難易度が高く、この問題に関連する問題はいくつかあります.次の更新...