【LeetCode】 best-time-to-buy-and-sell-stock-i ii iii iv
best-time-to-buy-and-sell-stock-i
Say you have an array for which the i th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
題意:株の毎日の価格を1つの配列で表し、配列のi番目の数は株のi日目の価格を表す.1回の取引しか許されない場合、つまり株を1株だけ買って売ることを許可し、最大の収益を求める.
分析:ダイナミックプランニング.前から後ろに配列を巡って、現在現れた最低価格を記録し、購入価格として、当日の価格で販売された収益を計算し、可能な最大収益として、遍歴の過程で現れた最大収益が求められる.
コード:時間O(n),空間O(1).
int maxProfit(vector &prices) { if (prices.size()<2) return 0; if (prices.size() == 2) prices[0] - prices[1]<0 ? 0 : prices[0] - prices[1]; int MAX = 0, min = prices[0], size = prices.size(); for (int i = 1; i < size; i++){ if (prices[i]>min) MAX = prices[i] - min>MAX ? prices[i] - min : MAX; else min = prices[i]; } return MAX <= 0 ? 0 : MAX;}
best-time-to-buy-and-sell-stock-ii
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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
テーマ:株の毎日の価格を1つの配列で表し、配列のi番目の数は株のi日目の価格を表す.取引回数は限定されませんが、一度に1株しか取引できません.つまり、手に持っている株は最大1株しか持っていないので、最大収益を求めます.
分析:貪欲法.前から後ろへ配列を巡って、その日の価格が前日の価格より高い限り、収益になります.
コード:時間O(n),空間O(1).int maxProfit_ii(vector &prices) {
//本題複数回の取引が許可されているので(毎回売ってから買わなければならない)、爆捜は使いにくい
//分析によると、利益を最大化するには、毎回谷で購入し、ピークで売るべきで、利益が最大で、操作回数が最も少ない.
//ダイナミックプランを使った方がシンプルかもしれないと思いますが、個人的には.
//株価が前日より高い場合、利益を得ることができ、すべての利益を加算して最大値を得ることができる
int len = prices.size();
vector change(len, 0);
int maxPro = 0;
for (int i = 1; i
change[i] = prices[i] - prices[i - 1];//すべての長さと下落を記録する
if (change[i]>0)
maxPro += change[i];//すべての長幅を累積すると、最大収益となります.
}
//ピーク減波谷はピークから谷までの要素が順次減算された和に等しく、公式を書くと相殺されていることがわかります.a, b, c, d, e ; e - a = e - d + d - c + c - b + b - a
return maxPro;
}
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).
題意:株の毎日の価格を1つの配列で表し、配列のi番目の数は株のi日目の価格を表す.最大2回取引して、手の上で最大1本の株を持つことしかできなくて、最大の収益を求めます.
分析:ダイナミックプランニング.i日目を境に、i日目までに1回の取引が行われる最大収益preprofit[i]と、i日目以降に1回の取引が行われる最大収益postProfit[i]を計算し、最後に遍歴するとmax{preprofit[i]+postProfit[i]}(0≦i≦n−1)が最大収益となる.i日目以前とi日目以降に1回行われる最大収益求法はBest Time to Buy and Sell Stock Iと同じである.
コード:時間O(n),空間O(n).
int maxProfit_iii(vector &prices) { int len = prices.size(); int firstBuy = INT_MAX; int firstSell = 0; int secondBuy = INT_MAX; int secondSell = 0; for (int i = 0; i { firstBuy = min(firstBuy, prices[i]); firstSell = max(firstSell, prices[i] - firstBuy); secondBuy = min(secondBuy, prices[i] - firstSell); secondSell = max(secondSell, prices[i] - secondBuy); } return secondSell; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Say you have an array for which the i th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
題意:株の毎日の価格を1つの配列で表し、配列のi番目の数は株のi日目の価格を表す.1回の取引しか許されない場合、つまり株を1株だけ買って売ることを許可し、最大の収益を求める.
分析:ダイナミックプランニング.前から後ろに配列を巡って、現在現れた最低価格を記録し、購入価格として、当日の価格で販売された収益を計算し、可能な最大収益として、遍歴の過程で現れた最大収益が求められる.
コード:時間O(n),空間O(1).
int maxProfit(vector &prices) { if (prices.size()<2) return 0; if (prices.size() == 2) prices[0] - prices[1]<0 ? 0 : prices[0] - prices[1]; int MAX = 0, min = prices[0], size = prices.size(); for (int i = 1; i < size; i++){ if (prices[i]>min) MAX = prices[i] - min>MAX ? prices[i] - min : MAX; else min = prices[i]; } return MAX <= 0 ? 0 : MAX;}
best-time-to-buy-and-sell-stock-ii
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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
テーマ:株の毎日の価格を1つの配列で表し、配列のi番目の数は株のi日目の価格を表す.取引回数は限定されませんが、一度に1株しか取引できません.つまり、手に持っている株は最大1株しか持っていないので、最大収益を求めます.
分析:貪欲法.前から後ろへ配列を巡って、その日の価格が前日の価格より高い限り、収益になります.
コード:時間O(n),空間O(1).int maxProfit_ii(vector &prices) {
//本題複数回の取引が許可されているので(毎回売ってから買わなければならない)、爆捜は使いにくい
//分析によると、利益を最大化するには、毎回谷で購入し、ピークで売るべきで、利益が最大で、操作回数が最も少ない.
//ダイナミックプランを使った方がシンプルかもしれないと思いますが、個人的には.
//株価が前日より高い場合、利益を得ることができ、すべての利益を加算して最大値を得ることができる
int len = prices.size();
vector change(len, 0);
int maxPro = 0;
for (int i = 1; i
change[i] = prices[i] - prices[i - 1];//すべての長さと下落を記録する
if (change[i]>0)
maxPro += change[i];//すべての長幅を累積すると、最大収益となります.
}
//ピーク減波谷はピークから谷までの要素が順次減算された和に等しく、公式を書くと相殺されていることがわかります.a, b, c, d, e ; e - a = e - d + d - c + c - b + b - a
return maxPro;
}
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).
題意:株の毎日の価格を1つの配列で表し、配列のi番目の数は株のi日目の価格を表す.最大2回取引して、手の上で最大1本の株を持つことしかできなくて、最大の収益を求めます.
分析:ダイナミックプランニング.i日目を境に、i日目までに1回の取引が行われる最大収益preprofit[i]と、i日目以降に1回の取引が行われる最大収益postProfit[i]を計算し、最後に遍歴するとmax{preprofit[i]+postProfit[i]}(0≦i≦n−1)が最大収益となる.i日目以前とi日目以降に1回行われる最大収益求法はBest Time to Buy and Sell Stock Iと同じである.
コード:時間O(n),空間O(n).
int maxProfit_iii(vector &prices) { int len = prices.size(); int firstBuy = INT_MAX; int firstSell = 0; int secondBuy = INT_MAX; int secondSell = 0; for (int i = 0; i { firstBuy = min(firstBuy, prices[i]); firstSell = max(firstSell, prices[i] - firstBuy); secondBuy = min(secondBuy, prices[i] - firstSell); secondSell = max(secondSell, prices[i] - secondBuy); } return secondSell; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
， leetcode https: //discuss.leetcode.com/topic/5934/is-it-best-solution-with-o-n-o-1 public class Solution { public int maxProfit( int [] prices) { int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE; int release1 = 0 , release2 = 0 ; for ( int i:prices){ // Assume we only have 0 money at first release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far. hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far. release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far. hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far. } return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1. } } best-time-to-buy-and-sell-stock-iv
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
： ， i i 。 k ， ， 。
： 。 ， i j ， i-1 j （ i i-1 ）， i-1 j-1 ， i （ i i-1 ）。 （ diff = prices[i] – prices[i – 1]）：
profit[i][j] = max(profit[i – 1][j], profit[i – 1][j – 1] + diff)
， ， ？ diff i i-1 ， i-1 ， ， profit[i – 1][j – 1] + diff j-1 ， j ， 。
i ， ？ i j ， 。
local[i][j] i ， j ； global[i][j] i ， j 。 （ diff = prices[i] – prices[i – 1]）：
local[i][j] = max(global[i – 1][j – 1] + max(diff, 0), local[i – 1][j] + diff)
global[i][j] = max(global[i – 1][j], local[i][j])
local[i – 1][j] + diff i i-1 。 ：http://www.cnblogs.com/grandyang/p/4295761.html
： O(n)， O(k)。
Best Time to Buy and Sell Stock III ， Dynamic programming ， ：
local global， Code Ganker ， k 。 local[i][j] i j ， 。 global[i][j] i j ， 。 ：
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])，
0 ， ， ， 。
， k prices ， k ， prices ， DP ， Best Time to Buy and Sell Stock II ， ， ：
class Solution {
public:
int maxProfit(int k, vector &prices) {
if (prices.empty()) return 0;
if (k >= prices.size()) return solveMaxProfit(prices);
int g[k + 1] = {0};
int l[k + 1] = {0};
for (int i = 0; i < prices.size() - 1; ++i) {
int diff = prices[i + 1] - prices[i];
for (int j = k; j >= 1; --j) {
l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
g[j] = max(g[j], l[j]);
}
}
return g[k];
}
int solveMaxProfit(vector &prices) {
int res = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] - prices[i - 1] > 0) {
res += prices[i] - prices[i - 1];
}
}
return res;
}
};