[JAVA] LeetCode 122 - Best Time to Buy and Sell Stock II

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit.

You may complete as many transactions as you like

(i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time

(i.e., you must sell the stock before you buy again).

 

i일(day)에 주식의 가격이 적힌 배열이 주어진다고 하자.

최대 이익을 얻기 위한 알고리즘을 설계하라.

당신은 당신이 원하는만큼 많은 거래를 할 수 있다.

다만, 동시에 여러 거래를 할 수 없다.

 

 

풀이 방법

처음 이 문제를 접근했을 때, 완탐으로 최대의 이익을 구하는 함수를 작성했었다.

스터디원들이 그렇게 접근하지 않아도 매우 심플한 방법으로 풀이를 할 수 있다는 말에

출퇴근 길에 고민하고 또 고민했는데, 도저히 아이디어가 떠오르지 않았다.

결국 스터디원들의 풀이를 보게되었고... 나는 머리를 한 대 맞은 것처럼 충격을 받았다.

 

이 문제는 '당신이 원하는 만큼 거래를 할 수 있다' 라는 조건을 잘 보아야 한다.

주식을 기간 내 한 번만 거래하는 것이 아닌, 내가 원할 때 사고 팔 수 있는 조건이다.

따라서, 심플하게 오늘 가격보다 내일 가격이 더 높을 때 팔면 되는 것이었다. (ㅠㅠ)

 

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