Lesson 9. Maximum slice problem - MaxProfit #1

1. 문제

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:
A[0] = 23171
A[1] = 21011
A[2] = 21123
A[3] = 21366
A[4] = 21013
A[5] = 21367
If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,
  int solution(vector<int> &A);

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:
A[0] = 23171
A[1] = 21011
A[2] = 21123
A[3] = 21366
A[4] = 21013
A[5] = 21367
the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [0..400,000];
  - each element of array A is an integer within the range [0..200,000].

 

주식 최대 이익을 구하는 문제.

index(P, Q): 매수일 \( (0 \leq P \leq Q < N) \)

A[index]: 가격

A[Q] - A[P]: 이익

적자면, return 0

 

예시) return 356 (A[5] - A[1])

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
23171	21011	21123	21366	21013	21367

 

 

2. 매개변수 제한

1. Vector A 크기: 0 ~ 400,000
2. Vector A 요소 값 범위: 0 ~ 200,000

 

3. 문제풀이 전략

• 매도일이 매수일보다 앞에 있을 수 없다. (P일에 샀으면, 최소 P+1일에 팔 수 있다)
• 따라서 P일에 사서, P+N일까지 최대 이익 값을 조사한다.

 

4. 코드 (C++)

• 전체 탐색 코드

int solution(vector<int> &A) {

    int max_profit = 0;
    for(size_t P = 0; P < A.size(); P++) //매수일(P)
    {
        for(size_t Q = P + 1; Q < A.size(); Q++) //매도일(Q)
        {
            int profit = A[Q] - A[P];
            if(profit > max_profit) max_profit = profit;
        }
    }

    return max_profit;
}

전체 탐색 코드 결과

---

• 정렬 사용 코드

전체 탐색보다 결과가 안좋다.

#include <algorithm>

int solution(vector<int> &A) {

    int max_profit = 0;
    for(size_t P = 0; P < A.size(); P++) //매수일(P)
    {
        vector<int> temp = A;
        sort(temp.begin() + P, temp.end());
        int profit = temp.back() - A[P]; //max_value - A[P]
        if(profit > max_profit) max_profit = profit;
    }

    return max_profit;
}

정렬 사용 코드 결과