算法-股票买卖问题

淡淡的烟草味﹌ 2024-04-18 13:35 8阅读 0赞

## 1. 股票买卖 ##

给定股价数组，数组元素为当天股价，可进行两次买入和卖出的交易，输出最大的收益

例如： 股价数组： prices = \{2,2,3,4,8,2,6\};

可分析得知:

*  第一次操作：买入 prices\[0\] = 2,卖出 prices\[4\] = 8，收益 6
 *  第二次操作：买入 prices\[5\] = 2,卖出 prices\[6\] = 6，收益 4

收益最大为 10

## 2. 解法 ##

使用两个数组模拟买卖操作，一个为从前往后遍历可获得的最大收益，另一个为从后往前遍历可获得的最大收益，最后合并两个数组，新数组中最大的元素即为最大收益。动态规划相关解法参考 [股票买卖问题完全解读][Link 1]

prices : {2,2,3,4,8,2,6}
    left   : [0,0,1,2,6,6,6]
    right  : [6,6,5,4,4,4,0]

public int maxProfit(int [] prices) {
        
         if (prices == null || prices.length == 0) return 0;
         int[] left = new int[prices.length];
         int[] right = new int[prices.lenght];
         return process(prices,left,right) ;
    }
    
    public int process(int[] prices, int[] left, int[] right) {
        
        // 计算从前往后遍历
        left[0] = 0; // 第一天买入并卖出收益
        int min = prices[0]; // 最低买入价格
        for(int i =1; i < left.length;i++) {
        
        // 第 i 天的最大利润为（第 i-1 天的利润）和（当前卖出价与最小买入价之差）的较大那个
            left[i] = Math.max(left[i-1],prices[i]-min);
            min = Math.min(min, prices[i]); // 更新最低买入价
        } 
        // 计算从后往前遍历
        right[right.length - 1] = 0; // 最后一天买入并卖出收益
        int max = prices[prices.length - 1]; // 最高卖出价格
        for(int i = right.length - 2; i >= 0;i--) {
        
        // 第 i 天的最大利润为（第 i+1 天的利润）和（最高卖出价与当前买入价之差）的较大那个
            right[i] = Math.max(right[i+1],max - prices[i]);
            max = Math.max(max, prices[i]); // 更新最高卖出价
        } 
    
        // O(n)找到最大值  
        for(int i=0; i<prices.length; i++){
          
            max = Math.max(max, left[i]+right[i]);  
        }        
        return max;  
    }

[Link 1]: https://blog.csdn.net/weixin_45505313/article/details/113397471