LeetCode 122 Best Time to Buy and Sell Stock II 풀러가기

문제

prices라는 int 배열이 주어진다.

각 배열은 날짜를 의미하고, 물건을 사는 날짜, 파는 날짜 각각 하나를 여러번에 걸쳐 골랐을 때 최고의 이익을 계산하여 리턴한다.

예를 들어, [7, 1, 5, 3, 6, 4]라는 배열이 주어졌을 때

1에 물건을 사고, 5에 물건을 팔 고, 3일에 팔고 6일에 샀을 때 총 이익이 7로, 가장 이익이 크다.

문제 분석

이익을 가장 많이 남기려면, 이익을 볼 수 있는 날은 무조건 봐야한다고 생각했다.

그래서 이전날보다 비용이 높다면, 무조건 이익을 더하도록 구현했다.

그래프로 따지면, 그래프가 상향일 때 모든 이익을 얻은 경우라고 생각하면 된다.

첫번째 시도

코드

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

결과 : 성공

Runtime

Memory

시간은 괜찮았는데

메모리가 낭비된 것 같아서, 또 다른 방법이 없을까 고민해봐야겠다.