Codility [ Lesson 9 | Maximum slice problem ] MaxProfit - JavaScript

문제

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,

function solution(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].

문제해석

하루 하루의 주식 시장의 값을 담은 배열이 주어진다.
주어지는 값 중 인덱스의 값은 day를 의미하고 높아질 수록 day 또한 올라간다. 언제 주식을 사서 언제 팔아야 가장 큰 이익을 볼 수 있는지 찾아서 그 값을 리턴해주는 문제이다.

문제풀이

문제는 A[i]와 A[i+1~N]의 값을 빼면서 차익이 가장 큰 값을 찾으면 되는 문제이지만 효율성을 따져야하기 때문에 O(N)으로 문제를 풀어야한다. O(N)의 효율성으로 이 문제를 해결 할 수 있는 카데인 알고리즘을 응용해야한다.

이 포스트를 읽으면 어떤 알고리즘인지 알기 쉬울 것이다.

코드

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    if(A.length === 1 || A.length === 0) return 0

    let find = A[0];
    let localMax = 0;
    let globalMax = 0;

    for(let i = 1; i<A.length; i++){
        localMax = A[i] - find;
        if(A[i] < find) find = A[i];

        globalMax = Math.max(localMax, globalMax);
    }

    return globalMax = globalMax < 0 ? 0 : globalMax
}

최종결과

출처

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/