문제
배열이 주어지며, 배열의 값은 주어진 주식의 가격이다.
하나의 주식을 매수할 날짜를 선택하고 해당 주식을 매도할 미래의 다른 날을 선택하여 이익을 극대화하려고 한다.
이 거래에서 얻을 수 있는 최대 이익을 반환하라.
이익을 얻을 수 없으면 0을 반환하라.
예시1
Input: prices = [7,1,5,3,6,4]
Output: 5
2일차(가격 = 1)에 구매하고 5일차(가격 = 6)에 판매. 이익 = 6-1 = 5.
2일차 구매 후 1일차 판매는 허용되지 않음.
예시2
Input: prices = [7,6,4,3,1]
Output: 0
이익을 얻을 수 없음.
첫 풀이 (틀린 답)
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
int profit;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
profit = prices[j] - prices[i];
if (profit > max) {
max = profit;
}
}
}
return max;
}
}이중 반복문을 사용하면 시간복잡도가 O(N^2)이라서 시간 초과가 발생한다.
처음에 이 방법을 사용해서 실패했다.
풀이
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int max = 0;
int min = Integer.MAX_VALUE;
int profit = 0;
for(int i=0; i<len; i++) {
if(prices[i] < min) {
min = prices[i];
}
else {
profit = prices[i] - min;
if(profit > max)
max = profit;
}
}
return max;
}
}- prices배열에서 최소값 min을 찾는다.
- 최소값 찾은 이후의 배열 인덱스부터 최대값을 찾는다.
- profit이 음수거나 0이면 max값이 0이므로 0이 반환된다.
