[leetcode #122] Best Time to Buy and Sell Stock II

Problem

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

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.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum 	profit of 0.

Constraints:

・ 1 <= prices.length <= 3 * 10⁴
・ 0 <= prices[i] <= 10⁴

Idea

주식을 거래할 때 최대 이익이 얼마인지 구하는 문제다.

주식을 가지고 있을 때와 가지고 있지 않을 때의 최대값을 각 step마다 구한 뒤, 마지막에 주식을 보유하고 있지 않을 때 최대값을 리턴하면 된다.
굳이 이렇게 하지 않더라도 각 단계마다 이득이 날 때마다 팔아버리면 답을 구할 수 있다.

Solution

class Solution {
    private int INITIAL_PROFIT = 0;
    public int maxProfit(int[] prices) {

        // index 0 → hold, 1 → not hold
        int[] dp = new int[]{-prices[0], INITIAL_PROFIT};

        for (int i=1; i < prices.length; i++) {
            dp[0] = Math.max(dp[0], dp[1] - prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
        }

        return dp[1];
    }
}

이득이 날 때마다 팔아버릴 때의 구현은 다음과 같다.

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

Reference

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