Java – optimal solution of maximum single sales profit algorithm

The input array is:

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

The mission is to find the maximum profit For example [3] – a [2] = 243 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 assumed to be 365, but it will explode on a larger input The time complexity of the code is O (N2), but it may be related to o (n) I can't really see how to avoid nesting here... Any pointer in the right direction will be appreciated

Solution

I think most people are wrong The question in this article is the biggest single sales profit question, which is a typical interview question

Best 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 check the original problem, OP is looking for profit because we can't travel in time (you) can't just compare the minimum and maximum values in the array