动态规划5：买股票问题

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