Leetcode - 121. Best Time to Buy and Sell Stock

리트코드 Best time to buy and sell stock 문제를 풀었다.

 

Example 1:

Input: [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.   Not 7-1 = 6, as selling price needs to be larger than buying price.

 

Example 2:

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

Output: 0

Explanation: In this case, no transaction is done, i.e. max profit = 0.

 

배열을 입력으로 받고 언제 사서 언제 팔면 이익이 가장 클지 계산하는 문제다.

 

[7, 1, 5, 3, 6, 4] 를 입력으로 받았다면 1에서 사서 6에서 팔아야 한다.

 

7,6,4,3,1은 갈수록 숫자가 내려가므로 낼 수 있는 최대 이익은 0이다.

 

코드는 아래와 같이 작성했다.

function maxProfit(prices: number[]): number {
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const profit = prices[j] - prices[i];
      if (profit > max) {
        max = profit;
      }
    }
  }
  return max;
};

 

앞에서부터 하나씩 읽으면서 최대 값을 갈아치운다.

0번째 - 1번째

0번째 - 2번째

0번째 - 3번째

....

....

반복한다.

그리고 최대 값을 리턴한다.