알고리즘 - Best Time to Buy and Sell Stock

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.

풀이

인덱스가 0은 1일이 되고 배열의 숫자는 그날 주식의 가격이 된다. 왼쪽부터 차례대로 날짜가 흘러갔고 배열이 주식의 가격이라면 가장 싸게사서 가장 비싸게 팔았을때 극대화 되는 수익을 리턴하는 문제이다. 두 값을 비교해야하기때문에 당연히 자연스럽게 이중포문을 떠올렸고 문제를 풀었다.

var maxProfit = function(prices) {
    let result = 0;
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[j] - prices[i] > 0) {
                result = prices[j] - prices[i]
            }
        }
    }
    return result
};

기본적으로 주어진 테케는 통과했지만 제출했을때 가장 최대의 경우의 배열을 받았을때 실행시간이 초과되어버리는 결과가 나왔다. 쉬운문제이고 가장 기본문제라 생각했는데 최대치에서 걸릴줄이야…

다시 생각해보면서 필요한게 무엇일까 생각해보았다. 일단 필요한건 배열을 순회함에 따라 가장 최소값을 갖는 값이 필요하고 최대 수익을 알아야하니 result 또한 필요하다. 그리고 최소값과 수익의 최대값이 필요하니 자바스크립트 기본 메소드중에 Math 를 활용하면 되지않을까 생각해서 다시 코드를 짜 보았다.

var maxProfit = function(prices) {
    let result = 0; // 최대 수익 결과 저장
    let min = prices[0]; // 배열의 가장 최소값
    for (let i = 1; i < prices.length; i++) {
        min = Math.min(prices[i], min); // 가장 작은값을 할당
        result = Math.max(result, prices[i] - min); // 최대 수익률 계산
    }
    return result
};