Buy and Sell Stock, with O( n log n ) time complexity

Question

EDIT:
I appreciate the help from both of you but I have to stay with the bound of O( n log n ) time completicty and have to use the divide and conquer technique with binary recursion. I did not make that very clear in the initial posting

I have an unsorted array of ints where I have to buy stock on the ith day and sell it on the jth day for a maximum profit where the ith(the smaller value) day has to come before the jth(the larger value) day. So far i have found a solution that returns the purchase and sell days( index values of the array) and the max profit but it has a O(n^2) time complexity and I am having a hard time getting to the O(n log n) time complexity and implementing divide and conquer

public static Profit BestProfit( int[] a, int i, int j )
{
   Profit bestProfit = new Profit();

   int n = j; 
   int maxProfit = 0;
   for(i = 0; i < n; i++)
   {
      for(j = i; j < n; j++)
      {
         if(a[j] - a[i] > maxProfit)
         {
            maxProfit = a[j] - a[i];
            bestProfit.setBuy( i );
            bestProfit.setSell( j );
            bestProfit.setMaxProfit( maxProfit );
         }
      }
   return bestProfit;
   } 

The params i is that start of the array and j in the end of the array The Profit class is a class that I created to hold buy, sell, and profit values.

The three case that I have found that I need to account for are the largest profit for the first half of the array, largest profit for the second half of the array, and the case where the smallest value is on the 1st half of the array and the largest value is on the 2nd half of the array(I have already completed this part of the problem with a simple min/max function that solves the final case).

I am stuck and any help with the divide and conquer implementation or tips of tricks would be greatly appreciated!

Answer 1

In O(n), pretty simple:

public static Profit bestProfit(int[] a, int begin, int end) {
    Profit bestProfit = new Profit();
    int min = a[begin];
    int max = a[begin];
    int index = begin;
    int buy = 0;
    int sell = 0;
    int minIndex = begin;
    int maxIndex;
    int maxProfit = 0;
    for (int i = begin; i < end; i++) {
        int n = a[i];
        if (n < min) {
            minIndex = index;
            min = n;
            max = n;
        } else if (max < n) {
            max = n;
            maxIndex = index;
            if (maxProfit < (max - min)) {
                maxProfit = max - min;
                buy = minIndex;
                sell = maxIndex;
            }
        }
        index++;
    }
    bestProfit.setBuy(buy);
    bestProfit.setSell(sell);
    bestProfit.setMaxProfit(maxProfit);
    return bestProfit;
}

EDITED: with divide and conquer:

public static int divideAndConquer(int[] a, int i, int j, Profit profit, int min) {
    int minResult;
    if (i+1 >= j) {
        minResult = Math.min(a[i], min);
        if (a[i] - min > profit.getMaxProfit()) {
            profit.setBuy(min);
            profit.setSell(a[i]);
            profit.setMaxProfit(a[i] - min);
        }
    } else {
        int n = (j+i)/2;
        minResult = divideAndConquer(a, i, n, profit, min);
        minResult = divideAndConquer(a, n, j, profit, minResult);
    }
    return minResult;
}

public static void main(String[] args) {
    int[] prices = {20, 31, 5, 7, 3, 4, 5, 6, 4, 0, 8, 7, 7, 4, 1,10};
    Profit profit =new Profit();
    divideAndConquer(prices, 0, prices.length, profit, Integer.MAX_VALUE);
    System.out.println(profit);
}