Interview Question for Software Engineer at Google:

Or in other words, find the two points where the difference between the two are the largest in the function.

"find the two points where the difference between the two are the largest in the function" - this is incorrect. You can not go back in time when it comes to stock trading :) e.g. {2,1,10} has a maximum loss of 1-2 = -1, but has a maximum difference of -9.

[11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps

Maintain two variables, min and max.

Whenever cur value of array is less than max then upadate min
do a diff between min and max and update curloss if it is less than curloss.

update max variable if value is greater than or equal to max

11 11 0
11 20 0
11 24 0
11 51 0
10 51 -41
10 99 -41
15 99 -84
1 99 -98
1 199 -198
75 199 -198

Slight error in my previous post given above:

[11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps

Maintain two variables, min and max.

Whenever cur value of array is less than max then upadate min
do a diff between min and max and update curloss if it is less than curloss.

update max variable if value is greater than or equal to max, dont update curloss variable here.

11 11 0
11 20 0
11 24 0
11 51 0
10 51 -41
10 99 -41
15 99 -84
1 99 -98
1 199 -98
75 199 -124

package asaf;

public class MaxLose {
    public static void main(String[] args) {
        int[] ticks = {5,7,4,2,77,8,9};
        int[] worseSell = new int[ticks.length];
        worseSell[worseSell.length-1] = ticks[ticks.length-1];

        for (int index=ticks.length-2; index>=0; index--) {
            worseSell[index] = Math.min(worseSell[index+1], ticks[index]);
        }

        int lose = 0;
        for (int index = 0; index < ticks.length; index++) {
            lose = Math.max(lose, ticks[index] - worseSell[index]);
        }
        System.out.println(lose);
    }

}

double WorstSell(double *values, int n)
{
    double maxBuySeenSoFar = 0.0;
    double minprofit = 0.0;

    // in-order lose most. we need to buy high and sell low. we can only sell after buying.
    for (int i = 0; i < n; ++i)
    {
        if (values[i] > maxBuySeenSoFar)
        {
            maxBuySeenSoFar = values[i];
        }
        else if (maxBuySeenSoFar - values[i] < minprofit)
        {
            minprofit = maxBuySeenSoFar - values[i];
        }
    }

    return minprofit;
}

Recursive way to solve this in n logn

public static int[] findMaxLost(int[] prices) {
        return rFindMaxLost(prices, 0, prices.length-1);
    }

    private static int[] rFindMaxLost(int[] prices, int p, int r) {

        if (p == r) {
            int[] ml_pos = new int[2];
        ml_pos[0] = p;
            ml_pos[1] = p;
            return ml_pos;
        }

        int q = (p + r) / 2;
        int[] l_ml_pos = rFindMaxLost(prices, p, q);
        int[] r_ml_pos = rFindMaxLost(prices, q + 1, r);

        /*find the max_min cross the center point q*/
        int[] m_ml_pos = new int[2];
        m_ml_pos[0] = findMax(prices, p, q);
        m_ml_pos[1] = findMin(prices, q + 1, r);

        if ((l_ml_pos[0] - l_ml_pos[1]) >= (m_ml_pos[0] - m_ml_pos[1])
                && (l_ml_pos[0] - l_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) {
            return l_ml_pos;
        } else if ((m_ml_pos[0] - m_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) {
            return m_ml_pos;
        } else {
            return r_ml_pos;
        }
    }

    private static int findMax(int[] prices, int p, int q) {
        int pos = 0;
        for (int i = p + 1; i <= q; i++) {
            if (prices[pos] < prices[i]) {
                pos = i;
            }
        }
        return pos;
    }

    private static int findMin(int[] prices, int q, int r) {
        int pos = 0;
        for (int i = q + 1; i <= r; i++) {
            if (prices[pos] > prices[i]) {
                pos = i;
            }
        }
        return pos;
    }

reader writer pointer soution. O(n)

public class MaxLose {
    public static void main(String[] args) {
        MaxLose m = new MaxLose();

        int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3};

        int max = m.maxLose(a);
        System.out.println(max);
    }

    private int maxLose(int[] a) {

        int b = 0, max = 0;

        for (int s = 1; s < a.length; s++) {
            if (a[b] <= a[s])
                b = s;
            else
                max = a[b] - a[s] > max ? a[b] - a[s] : max;
        }

        return max;
    }
}

Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left.
Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its left. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs.

Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left.
Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its right. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs.

public static int minPoint(List<Integer> list){
        if (!list.isEmpty()){
            int minPoint = list.get(0);
            return Math.min(minPoint - findMax(list),minPoint(list.subList(1, list.size()-1)));
        }
        return 0;

    }

    private static int findMax(List<Integer> list) {
        int max = list.get(0);
        for (int i=1; i<list.size(); ++i){
            if (list.get(i) > max){
                max = list.get(i);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3};
        List<Integer> list = new ArrayList<Integer>();
        for (int i=0; i<a.length; ++i){
            list.add(a[i]);
        }
        int min = minPoint(list);
        System.out.println(min);

    }

//Given the daily values of a stock, find how you can lose the most with one buy-sell trading.
//A[] -> {5, 8, 6, 3, 9, 3, 2, 7}
//B[] -> {0, 3,-2,-3,6,-6,-1, 5} ? diff A[i] = A[i] - A[i - 1]
//C[] -> {0, 0,-2,-5,0,-6,-7,-2} -> min(0, B[i - 1] + B[i])

public int[] looseMost(int[] A) {
 int minRes = 0;
 int sIdx = 0;
 int eIdx = 0;

 int currRes = 0;
 int csIdx = sIdx;

 int prevB = 0;
 int currB;
 int currC = 0;

 for (int i = 1; i < A.length; i++) {
  currB = A[i] - A[i - 1];
  currC = Math.min(0, currB + prevB);

  if (currC < minRes) {
   sIdx = csIdx;
   eIdx = i;
  }
  else if (currC == 0)
   csIdx = i;

  prevB = currB;
 }

return new int[] {sIdx, eIdx};
}

If I understand the question correctly, the task is to find the minimum consecutive sum of price differences, which is equivalent to a maximum consecutive sum algorithm (just google it). This can be solved in O(n) using a dynamic programming approach.