[Codility] Lesson9 - Maximum slice problem : MaxProfit

Problem

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].

app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

MaxProfit coding task - Learn to Code - Codility

How to solve

- 정보

N의 길이를 가진 배열 A, 주가를 나타냄, 배열 A의 index는 날짜

A[i]: i일의 주가

주식을 P일에 사고 Q일에 팔았을 때, 

A[Q]-A[P]의 최대 값 구하기 

 

- 구해야 하는것?

주식을 사고 팔았을 때, 이익의 최대 값 구하기

 

- 풀이

0 ~ 현재 idx의 최소 주가를 저장 (price_min)

현재 idx에서의 최대 이익:  현재 주가 A[idx] - 최소 주가 price_min

최대이익 갱신

 

**주의 사항**

A 배열의 크기 0, 1인 경우 확인

 

Solution(c++)

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();

    if(len == 0){
        return 0;
    }
    
    int price_min = A[0];
    int profit_max = 0;
    int profit_now;

    for(int i=1; i<len; i++){
        profit_now = A[i]-price_min;
        price_min = min(price_min, A[i]);
        profit_max = max(profit_max, profit_now);
    }

    if(profit_max < 0){
        return 0;
    }

    return profit_max;
}

Test Result

app.codility.com/demo/results/training75XDXN-CUA/

Test results - Codility