【困难】最佳股票买卖时机

深藏阁楼爱情的钟 2022-09-12 00:55 186阅读 0赞

#### 问题 ####

给定一个数组 arr 长度为 N，它的第 i 个元素是一支给定的股票在第 i 天的价格。  
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔 交易。  
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

#### 【动态规划思路】 ####

首先当 k >= N/2 时本题可同等于你可以完成任意笔交易。此时的思路为抓住所有的增长区间即为所求。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fFT4dFnY-1631929396635)(evernotecid://F1227914-1506-468F-92ED-DE7A9295E764/appyinxiangcom/27255310/ENResource/p281)\]

如图我们抓住每次机会买进卖出即可，就是最优解。  
那么当 k < N/2 时我们就需要进行讨论和动态规划了。  
一个很容易的思路，一个样本做行一个样本做列模型.  
此时对于 `dp[i][j]` 第 i 天进行 j 次交易所能获得的最大利润。  
在这个含义之上我们尝试进行推导动态转移方程。

分情况讨论，对于 `dp[i][j]` 两种情况  
（1）第 i 天不参与卖出  
（2）第 i 天参与卖出  
结果 = MAX(情况1，情况2)；  
**情况 1** 很简单其就等同于 `dp[i-1][j]`  
**情况 2**：这种情况我们可能需要进行一个枚举及

dp[i][j] = MAX(
    dp[i][j-1] + arr[i] - arr[i],
    dp[i-1][j-1] + arr[i] - arr[i-1],
    dp[i-2][j-1] + arr[i] - arr[i-2],
    ……
    dp[0][j-1] + arr[i] - arr[0]
    )

看起来这样是可行的，其语义就是 0-i 之前没卖，此时卖了的最大值。  
此时最耗时的就是这个【**情况2**】的枚举行为，让我们来思考一下有没有方法可以优化这个枚举行为。  
看下 `dp[i-1][j]` 的情况：

dp[i-1][j] = MAX(
    dp[i-1][j-1] + arr[i-1] - arr[i-1],
    dp[i-2][j-1] + arr[i-1] - arr[i-2],
    dp[i-3][j-1] + arr[i-1] - arr[i-3],
    ……
    dp[0][j-1] + arr[i] - arr[0]
    )

我们对公式做个提取如下：

dp[i][j] = MAX(
    dp[i][j-1]  - arr[i],
    dp[i-1][j-1] - arr[i-1],
    dp[i-2][j-1]  - arr[i-2],
    ……
    dp[0][j-1]  - arr[0]
    ) + arr[i]
    
    
    dp[i-1][j] = MAX(
    dp[i-1][j-1] - arr[i-1],
    dp[i-2][j-1] - arr[i-2],
    dp[i-3][j-1] - arr[i-3],
    ……
    dp[0][j-1] - arr[0]
    ) + arr[i-1]

此时 【**情况2**】max 的枚举计算是可以依赖之前的最优解的 `dp[i-1][j]` 情况 2 的 max 最大值，那么 `dp[i][j]` 就可以依赖此值省去枚举  
即：

dp[i][j]= MAX(dp[i-1][j]情况2 max ,dp[i][j-1] - arr[i]) + arr[i]

ok 理论存在，付诸实践

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

#### 题解 ####

package algorithmic.total.solution.common;
    
    /** * @program: algorithmic-total-solution * @description: 买卖股票的最佳时机 * 给定一个数组 arr 长度为 N，它的第 i 个元素是一支给定的股票在第 i 天的价格。 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔 交易。 * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 * @author: wangzibin **/
    public class Question4 { 
    
        public static void main(String[] args) { 
            int[] price=new int[]{ 9,3,4,9,5,1};
            System.out.println(getMaxProfit(price,2));
        }
    
    
        public static int getMaxProfit(int[] arr, int k) { 
            if (arr == null || arr.length < 1) { 
                return 0;
            }
            int length = arr.length;
            if (k >= length / 2) { 
                return getMaxProfit(arr);
            } else { 
                int[][] dp = new int[length][k + 1];
    
                for (int j = 1; j < k + 1; j++) { 
                    int preMax = dp[0][j-1]-arr[0];
                    for (int i = 1; i < length; i++) { 
                        preMax = Math.max(preMax, dp[i][j - 1] - arr[i]);
                        dp[i][j] = Math.max(preMax + arr[i], dp[i - 1][j]);
                    }
                }
                return dp[length - 1][k];
            }
        }
    
        private static int getMaxProfit(int[] arr) { 
            if (arr == null || arr.length < 1) { 
                return 0;
            }
            int buy = 0;
            int sum = 0;
            for (int i = 0; i < arr.length; i++) { 
                if (arr[buy] < arr[i]) { 
                    sum += arr[i] - arr[buy];
                }
                buy = i;
            }
            return sum;
        }
    
    }