[알고리즘] LeetCode - Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II - LeetCode

문제 설명

• 해당 날짜의 특정 주식 가격을 나타내는 정수형 배열 prices가 주어진다.
• 주식을 매수하고 주식을 매도했을 때 낼 수 있는 가장 높은 이익의 합을 반환해야 한다.
• 구매한 후 당일 즉시 판매할 수 있다.

문제 해결

• 배열의 연속된 요소 2개를 비교하여 양수일 때(그래프가 증가하는 경우)의 값들을 모두 합산하여 반환한다.
• 그래프를 그려보면 감소하는 것은 무시하고 증가하는 부분만을 합산하였을 때 가장 높은 이익의 합을 반환하는 것을 알 수 있다.

시간 복잡도

• O(N-1)

풀이 코드

class Solution {
    public int maxProfit(int[] prices) {
        int N = prices.length;
        int answer = 0;

        for (int i = 1; i < N; i++) {
            answer += Math.max(0, prices[i] - prices[i - 1]);
        }
        return answer;
    }
}

결과

시간	메모리
1 ms	44.3 MB