[Codility] 第九課 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].

Java 程式碼

class Solution {
    public int solution(int[] A) {
        boolean isFirst = false;
        int lastNum = 0;
        for(int i = 0; i < A.length;i++){
            for(int j = i+1; j < A.length;j++){
                int result = A[j] - A[i];
                
                if(isFirst){
                    lastNum = result;
                    isFirst = false;
                }else{
                     if(result > lastNum){
                        lastNum = result;
                     }
                }
                
               
            }
        }
        return lastNum;
    }
}

分數共拿 66%，時間複雜度的部分 fail了，希望最終結果是 O(n) 。
所以還需要再調整，一個 for 迴圈搞定。

任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想



感謝相關連結
https://www.codility.com/
https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/