Optimal solution for the maximum single sell profit algorithm

Question

The input array is:

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

Mission is to find maximum profit. E.g A[3] - A[2] = 243 and my code is:

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

The result is suppose to be 365 but it blows up on larger inputs. This code has a time complexity of O(N²) but is possible to do with O(N). I can't really see how to avoid nesting here... Any pointers in the right direction appreciated.

Answer 1

I think that most of you got it wrong. The problem in the post is the maximum single sell profit problem which is a typical interview question.

The most optimal solution:

    public int dynamicProgrammingSingleSellProfit(int[] arr) {
        if(arr.length == 0) {
            return 0;
        }
        int profit = 0;
        int cheapest = arr[0];

        for (int i = 0; i < arr.length; i++) {

            cheapest = Math.min(cheapest, arr[i]);
            profit = Math.max(profit, arr[i] - cheapest);

        }
        return profit;
    }

It has O(n) time and O(1) space complexity.

If you examine the original question the op is looking for profit and since we can't travel in time (yet) you can't just compare the minimum and the maximum in the array.