Best Time to Buy and Sell Stock 2

문제

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

Example 2:
Input: prices = [1,2,3,4,5]
Output: 4

Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
 
Constraints:
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

정수배열에는 주식의 가격이 주어진다. i일의 주식가격은 prices[i]

주식은 최대 한개만 살 수 있고 같은날에 사거나 팔 수 있다.

이때 얻을 수 있는 최대 수익을 찾는 문제이다.

---

풀이

예제 2번을 살펴보자.

i=0일때 사고, i=4일때 팔면 => 수익 4가 생긴다.

i=0일때 사고, i=1일때 팔고, 다시 사고, i=2일때 팔고... => 수익을 1씩 네번 챙길 수 있다.

 

중간에 숫자하나를 바꿔보았다.

[1,2,1,4,5]

i=0일때 사고, i=4일때 팔면 => 수익 4가 생긴다.

 

i=0, i=1 일때 수익1

i=2, i=3 일때 수익3

i=3, i=4 일때 수익1

=> 수익 5가 생긴다.

 

즉, 오름차순인 경우에 사고 팔면 최대 수익을 보장한다.

 

// 수익을 저장할 변수
int profit = 0;

// for loop 는 index 1부터 시작하여 이전 가격과 비교한다.
for (int i = 1; i < prices.length; i++) 

// 이전 가격보다 현재가격이 비싸다면 수익을 낼 수 있다.
// 수익을 추가한다.
if (price > prevPrice) {
	profit += price - prevPrice
}

---

결과

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}