[코딜리티] - Lesson 9.MaxProfit

안녕하세요 남갯입니다.

n^2 의 풀이

public int solution(int[] A) {
    // write your code in Java SE 8
    int result = 0;
    int sum = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = i + 1; j < A.length; j++) {
            sum = A[j] - A[i];
            result = Math.max(result, sum);
        }
    }
    return result;
}

퍼포먼스 타임 아웃남

https://app.codility.com/demo/results/trainingHXQ6T5-UKU/

n으로 풀어야함

public static int solution(int[] A) {
    // write your code in Java SE 8
    int[] copy = A.clone();
    Arrays.sort(A);
    int left = A.length;
    int right = 0;
    int strIdx = 0;
    int endIdx = A.length - 1;
    while (left > right && (strIdx != endIdx)) {
        for (int i = 0; i < A.length; i++) {
            if (copy[i] == A[strIdx]) {
                left = i;
            }
            if (copy[i] == A[endIdx]) {
                right = i;
            }
        }
        if (A[strIdx + 1] - A[strIdx] <= A[endIdx] - A[endIdx - 1]) {
            strIdx++;
        } else {
            endIdx--;
        }
    }
    return copy[right] - copy[left];
}

이것도 안되네