Lesson 9. Maximum slice problem - MaxProfit #2 (속도 개선-1)

1. 속도 개선 아이디어

정렬을 사용한 코드는 개선의 여지가 있다.

매번 정렬하지 말고, 필요할 때만 정렬하도록 수정할 수 있다.

 

알고리즘 수정

1. 정렬 후, 최대값 구하기
2. 매수가격(A[i])이 최대값(max_value)과 같지 않으면, 최대값 재활용
3. 매수가격(A[i])이 최대값(max_value)과 같으면, 최대값 다시 구하기

 

 

2. 코드 (C++)

#include <algorithm>

int getMaxPrice(vector<int> prices, int Q)
{
    sort(prices.begin() + Q, prices.end());
    return prices.back();
}

int solution(vector<int> &A) {

    if(A.empty()) return 0;

    int max_profit = 0;
    int max_value = getMaxPrice(A, 1);

    for(size_t P = 0; P < A.size(); P++) //매수일(P)
    {
        if(max_value == A[P])
        {
            max_value = getMaxPrice(A, P + 1);
        }

        int profit = max_value - A[P];
        if(profit > max_profit) max_profit = profit;
    }

    return max_profit;
}

 

 

 

3. 결과