Best Time to Buy and Sell Stock I && II && III

喜欢ヅ旅行 2022-08-27 05:58 139阅读 0赞

### 题目1：Best Time to Buy and Sell Stock ###

Say you have an array for which the ith 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.

**分析：**

题意给我们一个数组prices\[\], 用来表示股票每一天的价格,问我们如果“只多进行一次交易”(即买进之后再卖出), 应该在哪天买进，哪天卖出所获得的利润能达到最大值。

如：prices=\{1, 3, 4, 10, 1\};

那么最大的利润是第一天买进(价格为1),然后第四天卖出(价格为10), 利润最大为9

明白了题意之后，我们来看看能怎样解决这道题目。

由于是只能交易一次，而且必须先有“买进”，才能有“卖出”

因此我们只需要数组的最后一位往前扫描，依次得到哪一天的prices是最大的(设为maxPrices)，然后在算出和这一天前面的某一天prices\[i\]的差值 (maxPrices - prices\[i\])，如果大于最大的利润值，则更新最大利润值maxMoney;

**AC代码: **

public class Solution {
        
        public int maxProfit(int[] prices) {
            int size = prices.length;
            if (size == 0){
                return 0;
            }
            int maxPrice = prices[size-1];//初始化最大price
            int maxMoney = 0;//初始化利润值
            for (int i=size-1; i>=0; --i){
                maxPrice = maxPrice > prices[i] ? maxPrice : prices[i];//如果第i天的值大于最大price,则更新最大price的值
                maxMoney = maxMoney > (maxPrice - prices[i]) ? maxMoney : (maxPrice - prices[i]);//更新最大利润值
            }
            return maxMoney;
        }
    }

### 题目2：Best Time to Buy and Sell Stock II ###

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 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).

**分析：**

这道题目，关键是要理解题意，题意中和题目I是有点像，唯一不同的是这道题目可以进行多次交易，但是要注意的是，每次最多只能持有一支股票在手上，也就是说你要再买入的时候，必须先把手头上的这股票先卖掉！

举个例子：如Prices\[\] = \{1,3,4,10,2\};

这样子的话，你可以采取的方式有

1、第1天买入(price==1)，第2天卖出 (price==3), 第3天买入(price==4),第4天卖出(price==10)  ：   8

2、第1天买入(price==1)，第3天卖出(price==4)       ： 3

3、第2天买入 (price==3)，第3天卖出(price==4)       ： 1

4、第3天买入(price==4)，第4天卖出(price==10)     ： 6

5、第1天买入 (price==1)，第4天卖出(price==10)     ： 9

但其实如果仔细观察容易发现 :

3 - 1 = 2

4 - 3 = 1

10 - 4 = 6

然后result = 2 + 1 + 6 = 9

因此其实我们只是要找增长的序列对，并求出他们的差值的和

index :  1 ~~ prices.size()-1

通过这样分析的话，我们很容易知道其实只要从头到尾遍历，如果 prices\[index\] > prices\[index-1\]

**AC代码：**

public class Solution {
        public int maxProfit(int[] prices) {
            int profit = 0;
            int size = prices.length;
            if (size < 2){
                return profit;
            }
            for (int index=1; index<size; ++index){
                int value = prices[index] - prices[index-1];
                if (value > 0){
                    profit += value;
                }
            }
            return profit;
        }
    }

### 题目3： ###

### Best Time to Buy and Sell Stock III ###

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 two transactions.

Note:  
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

**分析：**

由于最多只可以进行两次交易，而且两次交易之间必须没有交集。

这题用DP来做.

那我们很容易想到，将数组划分成两块，左边一块 | 右边一块，我们只需要求出左边的最大利润,再求出右边的最大利润，然后相加起来就得到了利润的最大值

我们用

用left\[i\] 来表示\[0,...,i\]中的最大利润  
用right\[i\]来表示\[i,...,n-1\]上的最大利润

**AC代码：**

public class Solution {
        public int maxProfit(int[] prices) {
            int size = prices.length;
            if (size < 2)
                return 0;
            int[] left = new int[size];
            int[] right = new int[size];
            int minValue = prices[0];
            int maxValue = prices[size-1];
            for (int i=1; i<size; ++i){
                left[i] = left[i-1] > (prices[i] - minValue) ? left[i-1] : (prices[i] - minValue);
                minValue = minValue < prices[i] ? minValue : prices[i];
            }
            for (int i=size-2; i>=0; --i){
                right[i] = right[i+1] > (maxValue - prices[i]) ? right[i+1] : (maxValue - prices[i]);
                maxValue = maxValue > prices[i] ? maxValue : prices[i];
            }
            int profit=0;
            for (int i=0; i<size; ++i){
                profit = profit > (left[i] + right[i]) ? profit : (left[i] + right[i]);
            }
            return profit;
        }
    }