문제
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).
method signature 는 다음과 같다
public int maxProfit(int[] prices) {
}
Java
복사
특이한 점은 구매한 날을 b 번째 index 라 하고, 판매한 날을 s 번째 index 라 하면
prices[s] - prices[b]
Java
복사
로 발생되는 주식의 profit 을 모두 합쳐 최대값을 반환하는 문제이다.
풀고나서 solution 을 보니 나름 잘 푼거 같아 공유한다.
→ 이 그래프는 solution 에서 나와 있는 그래프 이다.
문제를 풀다보니 이러한 조건이 성립한다.(의도하고 푼게 아님;;)
•
3번째에 사서 6번째에 판매하는 값
•
3번째에 사서 4번째에서 팔고, 다시 4번째에서 사서 5번째에서 팔고, 다시 5번째에서 사서 6번째에서 판 값
이 두 값이 결국 같은 profit 이다.
class Solution {
public int maxProfit(int[] prices) {
int buy = prices[0];
int profit = 0;
int result = 0;
for (int i = 1; i < prices.length; i ++) {
buy = Math.min(buy, prices[i]);
int prev = profit;
profit = Math.max(profit, prices[i] - buy);
if (profit != prev && profit > 0) {
result += profit;
profit = 0;
buy = prices[i];
}
}
return result;
}
}
Java
복사
접근한 테스트 케이스는 아래와 같다
[7,1,5,3,6,4] // 기본 제공
[1,3,7,1,3,7]
[1,9,7,1,9,7]
Java
복사
처음에 풀었을 때는 문제를 잘못 이해해 판매한 곳(profit 값이 갱신 된 곳)에서 buy 를 하지 못하는줄 알고 고민 했었으나 example을 보면 판매한 곳에서 바로 구매하는 것을 확인할 수 있었다.
leetcode 의 예시들
설명
•
buy: 구매한 가격
•
profit: 해당하는 index (현재 날짜)에서 판매 했을때 취한 '이득'
•
prev: profit 을 비교하기 위해 임시로 이전 profit 을 저장한 '이득'
•
result: 모든 profit 을 더해 반환하는 값
if (profit != prev && profit > 0) {
Java
복사
위와 같은 조건을 선택한 이유는 판매하여 발생한 이득이 변경된 시점에 buy, profit 을 초기화 하기 위해서 이다.
이 문제는
와 연관이 있다.
