Codility_MaxProfit

9-1. MaxProfit

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,

class Solution { public int solution(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].

N개의 정수로 구성된 배열 A가 주어집니다. 이 배열은 N일 동안의 주식 가격을 나타냅니다. 만약 P일에 주식을 사고 Q일에 팔았다면, 여기서 0 ≤ P ≤ Q < N, 그러면 이러한 거래의 이익은 A[Q] − A[P]와 같습니다. 단, A[Q] ≥ A[P]인 경우에만 이익이 발생합니다. 그렇지 않으면 거래는 A[P] − A[Q]만큼의 손실을 가져옵니다.

예를 들어, 다음과 같은 6개의 요소로 구성된 배열 A를 고려해보세요:

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

만약 0일에 주식을 사고 2일에 팔았다면, A[2] − A[0] = 21123 − 23171 = −2048이므로 2048의 손실이 발생합니다. 만약 4일에 주식을 사고 5일에 팔았다면, A[5] − A[4] = 21367 − 21013 = 354이므로 354의 이익이 발생합니다. 최대 가능한 이익은 356이며, 이는 1일에 주식을 사고 5일에 팔았을 때 발생합니다.

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(int[] A); 
}

N일 동안의 주식 가격을 나타내는 N개의 정수로 구성된 배열 A가 주어졌을 때, 이 기간 동안 한 번의 거래로 얻을 수 있는 최대 이익을 반환하는 함수를 작성하세요. 만약 이익을 얻을 수 없는 경우 함수는 0을 반환해야 합니다.

예를 들어, 다음과 같은 6개의 요소로 구성된 배열 A가 주어졌을 때:

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

함수는 356을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [0…400,000] 범위 내의 정수입니다.
배열 A의 각 요소는 [0…200,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        if (A.length == 0) {
            return 0; // 배열이 비어 있는 경우
        }

        int minPrice = A[0];
        int maxProfit = 0;

        for (int i = 1; i < A.length; i++) {
            maxProfit = Math.max(maxProfit, A[i] - minPrice);
            minPrice = Math.min(minPrice, A[i]);
        }

        return maxProfit;
    }
}

사용함수 : Math.max(a, b) -> a와 b중 더 큰값을 반환

현재까지의 최대 이익(maxProfit)과 현재 가격에서 최소 가격을 뺀 값(A[i] - minPrice)을 비교하여 더 큰 값을 maxProfit에 저장하고 이를 통해 최대 이익을 업데이트

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/