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

---

첫 답안

답은 다 맞았지만 퍼포먼스에서 일부 실패, O(N)² 때문이다.

class Solution {
    public int solution(int[] A) {
        int max = 0;
        for(int i=0; i<A.length-1; i++) {
            int priceBought = A[i];
            for(int j=(i+1); j<A.length;j++) {
                int priceSold = A[j];
                int profit = priceSold - priceBought;
                if (profit > max) {
                    max = profit;
                }
            }
        }
        return max > 0 ? max : 0;
    }
}

---

두번째 답안

퍼포먼스 통과를 위해 정렬을 사용했지만 역시나 퍼포먼스에서 실패하였다.

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Pair[] pairs = new Pair[A.length];
        for(int i=0; i<A.length; i++) {
            Pair pair = new Pair(A[i], i);

            pairs[i] = pair;
        }

        Arrays.sort(pairs);
        int max = 0;

        for(int i=0; i<pairs.length-1; i++) {
            Pair left = pairs[i];
            for(int j=(pairs.length-1); j>i; j--) {
                Pair right = pairs[j];
                if(right.getIndex() <= left.getIndex()) {
                    continue;
                } else {
                    int profit = right.getValue() - left.getValue();
                    if (profit > max) {
                        max = profit;
                        break;
                    }
                };                
            }
        }
        return max;
    }
}

class Pair implements Comparable<Pair> {
    private int index;
    private int value;

    public Pair(int value, int index) {
        this.value = value;
        this.index = index;
    }
    
    public int getIndex() {
        return this.index;
    }

    public int getValue() {
        return this.value;
    }

	@Override
	public int compareTo(Pair p) {
		return this.value - p.getValue();
	}
}

---

베스트 답안

다이나믹 프로그래밍이라는 것에 대해 알아야 한다고 한다.
이곳에서 잘 설명해주고 있다.

function solution(A) {
    if(A.length === 1 || A.length === 0) return 0;

    let minPrice = A[0];
    let localMaxProfit = 0;
    let globalMaxProfit = 0;

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

        globalMaxProfit = Math.max(localMaxProfit, globalMaxProfit);
    }

    if(globalMaxProfit < 0) return 0; //이익을 보는 경우가 없이, 손해만 나는 경우

    return globalMaxProfit;
}