Lesson9. Maximum slice problem - MaxProfit

MaxProfit - Given a log of stock prices compute the maximum possible earning.

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

문제요약

N개의 정수 배열 A가 주어진다. A는 연속된 N일 기간동안 그 날의 주식가격이다. P일에 사서 Q일에 판다고하면 0<=P<=Q<N이고, 수익은 A[Q]-A[P]가 된다. 반면 A[P] > A[Q]가 되면 손실이 발생한다.

주어진 A에서 최대 수익을 계산하여 반환, 수익을 얻을 수 없다면 0을 반환한다.

Assume that:

N is an integer within the range [0..400,000];

each element of array A is an integer within the range [0..200,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

풀이

A의 i에 대해 i일에 판다고 하면 [0, ..., i-1] 중 가장 작은 값을 빼주면 i일에 팔 때 가장 큰 수익을 계산 할 수 있다. 즉, A를 순차적으로 검색하면서 이전까지의 최소값을 별도로 계산해서 유지하고 그 값을 현재 값에서 빼주면 그 날의 최대 수익을 알 수 있고 이 값들의 최대 값을 구하면 된다.