121. Best Time to Buy and Sell S

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

我们可以用两种方法解决这个问题
第一种方法，首先，为了更好地理解动态规划的过程，我们开多个数组以便更好的理解

minPrice[i]: 到第i天为止的最低价格
maxProfit[i]: 到第i天能获得的最大收益
maxProfit[i] = max(maxProfit[i-1], prices[i] - minPrice[i-1])

此时，时间复杂度为O(n)，空间复杂度为O(n)，我们可以通过将数组变为变量使空间复杂度变为O(1)。

Solution

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 1) {return 0;}
        
        //int[] minPrice = new int[prices.length];
        //int[] maxProfit = new int[prices.length];
        //minPrice[0] = prices[0];
        //maxProfit[0] = 0;
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++){
            //minPrice[i] = Math.min(minPrice[i-1], prices[i]);
            //maxProfit[i] = Math.max(maxProfit[i-1], prices[i] - minPrice[i-1]);
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
        //return maxProfit[n-1];
    }
}

第二种方法，可以将该问题转换为max subarray问题
从受益的角度出发，状态转移矩阵为P[i] = max(gain[i], P[i-1] + gain[i])
如果P[i-1]为负，则没有必要从前面开始。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int sum = 0;
        int flag = 0;
        for (int i = 1; i < n; i++){
            flag = Math.max(0, flag + prices[i] - prices[i-1]);
            sum = Math.max(flag, sum);
        }
        return sum;
        
    }
}