.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
한번의 거래로 낼 수 있는 최대 이익을 산출하라.
•
설명
1일 때 사서 6일 때 팔면 5의 이익을 얻는다.
My solution
max를 업데이트하는 식으로 브루트 포스로 풀었다.
Code
const BestTimeToBuyAndSell = function (s) {
let max = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j < s.length; j++) {
if (s[j] - s[i] > max) {
max = s[j] - s[i];
}
}
}
return max;
};
JavaScript
복사
시간복잡도 O(n)라서 효율성에서 떨어진다.
Solution
1. 브루트 포스로 계산
내 풀이와 동일하다.
2. 저점과 현재 값과의 차이 계산
시각화해보면 직관으로 풀이가 떠오를 수 있다.
한칸씩 이동하면서 이전 최저점과 현재 값을 빼면서 그 값을 가지고 max를 업데이트한다.
const BestTimeToBuyAndSell = function (s) {
let min = Number.MAX_SAFE_INTEGER;
let max = 0;
for (let i = 0; i < s.length; i++) {
min = Math.min(min, s[i]);
max = Math.max(max, s[i] - min);
}
return max;
};
JavaScript
복사
