Algorithm
[leet] Best Time to Buy and Sell Stock
향찡
2021. 12. 13. 23:34
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Best Time to Buy and Sell Stock - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Input 배열이 주어졌을 때 최대 이익을 구하는 문제입니다.
배열의 순서가 day라고 가정해서, 최대 이익의 발생값을 구하는 문제입니다.
public class Best_Time_to_Buy_and_Sell_Stock {
public static void main(String[] args) {
int[] prices = new int[]{7, 1, 5, 3, 6, 4};
Best_Time_to_Buy_and_Sell_Stock b = new Best_Time_to_Buy_and_Sell_Stock();
System.out.println(b.maxProfit(prices));
}
public int maxProfit(int[] prices) {
int min_val = Integer.MAX_VALUE; // 값 초기화
int max_profit = 0;
for(int i=0; i<prices.length; i++) {
if(prices[i] < min_val) {
min_val = prices[i];
}
if(prices[i] - min_val > max_profit) {
max_profit = prices[i] - min_val;
}
}
return max_profit;
}
// O(n^2)
public int maxProfit2(int[] prices) {
int max = 0;
for(int i = 0; i < prices.length -1; i++) {
for(int j = i+1; j< prices.length; j++) {
if(max < prices[j] - prices[i]) {
max = prices[j] - prices[i];
}
}
}
if (max > 0) {
return max;
} else {
return 0;
}
}
}배운 것
최솟값을 초기화할 때 Integer.MAX_VALUE로 초기화를 한다.
Reference