vamsu
7/29/2018 - 4:29 PM

Maximum profit earned by buying and selling

Given a list containing future prediction of share prices, find maximum profit that can be earned by buying and selling shares any number of times with constraint that a new transaction can only start after previous transaction is complete. i.e. we can only hold at-most one share at a time.

MaxProfitBuySell.java
content_copyfile_download
import java.util.*;
public class MaxProfitBuySell {
    public static void main(String args[]) {
        MaxProfitBuySell profit = new MaxProfitBuySell();
        int[][] input = {
          null,
          {},
          {1},
          {2,3},
          {1,5,2,3,7,6,4,5},
          {3,3,3},
          {1,2,3,4,5},
          {5,4,3,2,1}
        };
        
        for(int i=0; i< input.length; i++) {
            System.out.println("Input: " + Arrays.toString(input[i]) + " Result: " + profit.find(input[i]));
        }
    }
    
    private int find(int[] input) {
        if(input == null || input.length < 2) {
            return 0;
        }
        int profit = 0;
        int buyIndex = 0;
        for(int i=1; i<input.length; i++) {
            //Check if this is good buy point
            if(input[i-1] > input[i]) {
                buyIndex = i;
            }
            //Check if can sell here
            //Check the second condition is also checking for the last element
            //Very important to show we are thinking of the problem
            if(input[i-1] < input[i] && 
              (i + 1 == input.length || input[i] > input[i+1])) {
                profit += input[i]-input[buyIndex];
            }
        }
        return profit;
    }
}