[leetcode #123] Best Time to Buy and Sell Stock III

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

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

Example 4:

Input: prices = [1]
Output: 0

Constraints:

・ 1 <= prices.length <= 10⁵
・ 0 <= prices[i] <= 10⁵

Idea

이전에 stock 팔아 최대 이득을 보는 문제와 비슷할 거라 생각했는데, 조건이 약간 더 까다롭다. Transaction을 최대 2번까지 할 수 있다는 제약사항 때문이다. 어떻게 풀어야 하나 한참을 고민했는데 결국 못 풀어 다른 블로그를 참조했다.

생각보다 코드 수가 너무 짧고, prices 개수만큼 dp를 만들지도 않아 문제를 푼 사람이 대단하다고 생각했다.

최대 두 번의 거래가 있으며, 주식을 사는 가격과 파는 가격을 두 번의 거래 각각에 저장한다. 첫 번째 거래의 사는 가격은 전체 주식 가격의 최소값이 되며, 파는 가격은 전체 주식 가격의 최대값이 된다. 두 번째 거래에서 사는 가격은 첫 번째 거래에서 이득을 본 만큼을 뺀 값의 최소값이 된다. 이렇게 해야 두번째 거래에서 최대의 이득을 볼 수 있기 때문이다. 첫 번째 거래와 두 번째 거래에서 차이가 없다면 거래 하나로 최대의 이득을 볼 수 있는 것이다. 전체 주식 가격을 전부 탐색한 뒤 두 번째 거래에서 팔아 이득을 본 값을 리턴하면 된다.

Solution

class Solution {
    public int maxProfit(int[] prices) {
        int[] buy = new int[]{ Integer.MAX_VALUE, Integer.MAX_VALUE };
        int[] sell = new int[2];

        for (int price : prices) {
            buy[0] = Math.min(buy[0], price);
            sell[0] = Math.max(sell[0], price - buy[0]);
            buy[1] = Math.min(buy[1], price - sell[0]);
            sell[1] = Math.max(sell[1], price - buy[1]);
        }

        return sell[1];
    }
}

Reference

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://gracefulsoul.github.io/leetcode/best-time-to-buy-and-sell-stock-iii/