<Easy> Best Time to Buy and Sell Stock (LeetCode : C#)

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

📕 문제 설명

i번째 날의 주식 가격이 적힌 배열이 주어질 때 최대로 얻을 수 있는 이익 반환하기 (특정 날에 산 후 특정 날에 팔아야 함)

• Input
  i번쨰 날의 주식 가격 (int[])
• Output
  최대 이익

예제

풀이 1.

1) 왼쪽 dp: 현재 index에서 가장 최소로 샀을 때의 가격
2) 오른쪽 dp: 현재 index에서 가장 최대로 팔았을 때의 가격
3) 최종적으로 돌면서 오른쪽 dp 값 - 왼쪽 dp 값들 중 최대 값 return

public class Solution {
    public int MaxProfit(int[] prices) {

        int[] leftMinDp = new int[prices.Length];
        int[] rightMaxDp = new int[prices.Length];
        int answer = 0;

        leftMinDp[0] = prices[0];
        rightMaxDp[prices.Length - 1] = prices[prices.Length - 1];
        
        for (int i = 1; i < prices.Length; i++)
        {
            leftMinDp[i] = Math.Min(leftMinDp[i - 1], prices[i]);
        }

        for (int i = prices.Length - 2; i >= 0; i--)
        {
            rightMaxDp[i] = Math.Max(rightMaxDp[i + 1], prices[i]);
        }

        for (int i = 0; i < prices.Length; i++)
        {
            Console.WriteLine(rightMaxDp[i]);
            answer = Math.Max(answer, rightMaxDp[i] - leftMinDp[i]);
        }


        return answer;
    }
}

결과 1.

풀이 2.

그냥 한 바퀴 돌면서 max에는 똑같이 현재 가격 - 최소 값 중 큰 값으로 넣고, minBuy에는 살 수 있는 가격 중 최소로 계속 넣어주기

public class Solution {
    public int MaxProfit(int[] prices) {
        int max = 0;
        int minBuy = prices[0];
        for (int i = 0; i < prices.Length; i++)
        {
            max = Math.Max(max, prices[i] - minBuy);
            minBuy = Math.Min(minBuy, prices[i]);
        }
        return max;
    }
}

결과 2.

(제일 좋은 풀이랑 시간차 거의 없음)