7天内价格走势如下[7, 1, 5, 3, 6, 4]。
注明： 1次交易： 买+卖算一次，但必须先买入再卖出，且只能同时同时拥有一支
1. 问这7天内只能交易一次时，能获取的最大利润是多少？
一个遍历走起， 只要找到当前值与之前最小值的差值，其max即为所求
function res(arr) {
const len = arr.length;
let min = arr[0];
let diff = 0;
for(let i=0; i<len; i++) {
if(arr[i] - min > diff) {
diff = arr[i] - min;
}
if(arr[i] < min) {
min = arr[i];
}
}
return diff;
}
2. 问这7天内能交易任意次时，能获取的最大利润是多少？
顺着上一题的思路，可尝试定义f(n)为第n天的最大收益
前一天的收益为f(n-1)，两者的关系为：
f(n) = max(前一天如果持有， 可卖出,可不动；前一天如果没有，可买入,可不动)
所以需要二维数组记录第n天的最大收益
定义状态： f(n, i)， n 表示第n天，i取值为0, 1表示当前未持有/持有股票.
状态转移：
f(n, 0) = max(f(n-1, 0), f(n-1, 1) + arr[n]) // 第n天手中没有股票时的收益 = max(前一天也没有股票不动，前一天有股票今天卖出)
f(n, 1) = max(f(n-1, 0) - arr[n], f(n-1, 1)) // 第n天手中有股票时的收益 = max(前一天没有股票今天买入，前一天有股票今天不动)
最终所求值即为f(n-1, 0)， 最后一天一定是卖出后的收益更大
初始值:
f(0, 0) = 0; // 第一天不买入 0
f(0, 1) = -arr[0] // 第一天买入
function maxProfit(arr) {
let data = [];
const len = arr.length;
// 初始化二维数组
for(let i=0;i < len;i++) {
data[i] = [];
}
// 初始值
data[0][0] = 0;
data[0][1] = -data[0];
for(let i = 1; i < len; i++) {
data[i][0] = Math.max(data[i-1][0], data[i-1][1] + arr[i]);
data[i][1] = Math.max(data[i-1][0] - arr[i], data[i-1][1]);
}
return data[len-1][0];
}
3. 问这7天最多只能交易K次时，能获得的最大利润是多少？
基于第二问，在交易时还需要考虑交易次数的限制，所以定义状态时，还需要添加一维状态
定义状态: f(n, k, i) 为第n天交易k次时的最大收益，其中i取值为1，0表示当天是否持有股票
状态转移方程:
f(n, k, 0) = max(f(n-1, k, 0), f(n-1, k, 1) + arr[i])
f(n, k, 1) = max(f(n-1, k-1, 0) - arr[i], f(n-1, k, 1))
最终 max(f(n-1, 0, 0), f(n-1, 1, 0), ... f(n-1, K, 0) )为所求.
function maxProfit(arr, K){
const len = arr.length;
// 初始化一个3维数组
let data = [];
for(let i=0; i < len; i++) {
data[i] = createTwoDimArr(K+1, 2);
}
// 初始值的设置会略有不同
// data[i][0][0] 第i天，K为0，且手中没有，说明从未购买过，都为0
// data[0][k][0] 第0天，且手中没有时，说明从未交易过, 为0
data[0][0][0] = 0;
let max = 0;
for(let k = 1; k <= K; k++) {
data[0][k][0] = 0; // 第0天未持有，都是0
data[0][k][1] = -arr[0]; // 第0天持有时，只交易了一次，为第0天购入
for(let i = 1; i< len; i++) {
data[i][0][0] = 0;
data[i][k][0] = Math.max(data[i-1][k][0], data[i-1][k][1] + arr[i]);
data[i][k][1] = Math.max(data[i-1][k-1][0] - arr[i], data[i-1][k][1]);
}
if(data[len-1][k][0] > max) {
max = data[len-1][k][0];
}
}
return max;
function createTwoDimArr(m,n) {
let arr = [];
for(let i = 0; i<m; i++) {
arr[i] = new Array(n);
}
return arr;
}
}
