Best Time to Buy and Sell Stock

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Easy

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/BestTimetoBuyandSellStock/

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

Problem

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [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.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Solution

public class Solution
{
    public int MaxProfit(int[] prices)
    {
        int res = 0;
        int min = 99999;

        for (int i = 0; i < prices.Length; i++)
        {
            if (prices[i] < min)
            {
                min = prices[i];
            }
            else if (res < prices[i] - min)
            {
                res = prices[i] - min;
            }
        }

        return res;
    }
}

Comment

• 알고리즘 아이디어는 @Beomjoon Park 에게 있음을 밝힙니다.
• res : result, 현재까지의 최댓값을 저장.
• min : 최솟값. (가장 낮은 지점을 (현재까지의) 저장), 바로 첫값이 들어왔을 때 해당 값을 최솟값으로 초기화해줘야 하므로 int.MaxValue 혹은, constraint로 지정된 최댓값보다 더 큰 값으로 초기화.

How Algorithm Works

• prices를 0th~p.Length까지 선형적으로 for문으로 서치.
• 만약 현재 저장된 최솟값보다 pointer의 값이 작다면, 포인터의 값으로 최솟값을 바꾸어준다.
• 만약 그렇지 않다면(2번에서 분기), 현재 pointer를 파는 시점으로 생각했을 때의 이윤을 저장된 result 값과 비교하고, 더 크다면 최댓값에 저장한다.
• 0->Length의 방향성으로 인해 주식이 없는 상태에서 주식을 파는 등의 nonsense한 상황을 막을 수 있으며, min 값을 저장함으로써 현재 시점에서 가능한 최솟값을 표시하여 모든 경우를 체크 가능.