문제
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
내 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public int maxProfit(int[] prices) {
//풀이법 : 첫번째 값부터 비교하면서 최저값 인덱스, 최대값 인덱스 저장한다. 최대값 인덱스는 그 다음값보다 큰지도 비교한다. (다음 값이 더 크면 다음에 파는게 더 큰 이득이니까)
// 최댓값 인덱스가 최솟값 인덱스보다 큰 경우, 최소에 사서 최대에 팔 수 있기에 프로핏 값 계산한다.
//solution : save the lowest, highest price's index. The highest price's index should be larger than the next index's price.
//if the highest price's index is larger than the lowest price's index , calculate profit.
int lowIndex =0;
int highIndex=0;
int profit=0;
for(int i =0; i<prices.length; i++){
if(prices[i]<prices[lowIndex]){
lowIndex=i;
}else if(prices[i]>prices[lowIndex]){
//if price is higher than the lowest price and tomorrow's price, it is the best to sell today and buy another stock tomorrow.
if(i!=prices.length-1){
//check if today is the last day. (If it does, don't have to compare with tomorrow's price)
if(prices[i]>prices[i+1]){
highIndex=i;
}
}else{
highIndex=i;
}
}
if((highIndex > lowIndex)){
profit += prices[highIndex]-prices[lowIndex];
lowIndex=i+1;
}
}
return profit;
}
}