CareerCup

You can see it as a path:

7
                      / 
   6                6
  /  \               /
5     \     5     /
         \   /  \  /    
          \ /    4   
          3

(Formatting is giving me a hard time.. but you know what i mean)

If the last transaction is BUY - as long as its going up you keep the stock and the moment it starts going down (arr[i] < arr[i-1]) you have to SELL (on the previous day - i-1)

If the last transaction is SELL - as long as its going down you wait and the moment it starts going up again (arr[i] > arr[i-1]) you BUY at the cheapest price (on the previous day - i-1)

An edge case is on the last day - if you still hold the stock and the last day is higher than the day before - you just sell it.

I assume that one can purchase stock only when s/he hasn't any stock on hand.

Pretty much its finding sequential periods where is consecutively going up

List<Tupple<int, int>> findMaxProfit(List<int> stockvalues) {
	List<Tupple<int, int>> transactions = new List<Tupple<int, int>>()
	int currentStart = 0;
	for (int i=1; i < stockvalues.length; i++) {
		if(stockvalues[i-1] > stockvalues[i]) {
			if(currentStart != i-1) // If its not the same data
			{
				transactions.add(new Tuple<int, int>(currentStart, i-1))
			}

			currentStart = i;
		}
	}

	// Handling when even the last day was still going up
	if(stockvalues[currentstart] < stockvalues[stockvalues.length - 1]) {
		transactions.add(new Tuple<int, int>(currentstart, stockvalues.length - 1)
	}

	return transactions;
}

Assume profit is for the end of the day of the last purchased

public static long findMaxProfit(int[] stockPrices) {
   int curStockPrice = stockPrices[stockPrices.length-1];
   long profit = 0;

   for (int pricePaid : stockPrices) {
      profit += curStockPrice-pricePaid;
   }

return profit;
}

public static int findProfit(List<Integer> transactions){
int profit = 0;
if(transactions==null || transactions.size()<2){
return profit;
}
int buyPrice = transactions.get(0);
for(int currentPrice : transactions){
if(currentPrice>buyPrice){
profit = profit + (currentPrice - buyPrice);
buyPrice = currentPrice;
}else {
buyPrice = currentPrice;
}
}
return profit;
}

public static int findProfit(List<Integer> transactions){
        int profit = 0;
        if(transactions==null || transactions.size()<2){
            return profit;
        }
        int buyPrice = transactions.get(0);
        for(int currentPrice : transactions){
            if(currentPrice>buyPrice){
                profit = profit + (currentPrice - buyPrice);
                buyPrice = currentPrice;
            }else {
                buyPrice = currentPrice;
            }
        }
        return profit;
    }

public static int findProfit(List<Integer> transactions){
        int profit = 0;
        if(transactions==null || transactions.size()<2){
            return profit;
        }
        int buyPrice = transactions.get(0);
        for(int currentPrice : transactions){
            if(currentPrice>buyPrice){
                profit = profit + (currentPrice - buyPrice);
                buyPrice = currentPrice;
            }else {
                buyPrice = currentPrice;
            }
        }
        return profit;
    }

public static int findProfit(List<Integer> transactions){
        int profit = 0;
        if(transactions==null || transactions.size()<2){
            return profit;
        }
        int buyPrice = transactions.get(0);
        for(int currentPrice : transactions){
            if(currentPrice>buyPrice){
                profit = profit + (currentPrice - buyPrice);
                buyPrice = currentPrice;
            }else {
                buyPrice = currentPrice;
            }
        }
        return profit;
    }

l = [7,5,6,3,5,5,6,4,6,7,1]
import random
#l= [random.randrange(1,10) for l in range(10)]

ser=[]

#i=0
i=0
s=[l[i]]
mp=0 #stores highest possible profit for whole session
lp=0 #stores profit for a single series

print ('i=%d l[i]=%d lp=%d mp=%d' %(i,l[i],lp, mp))

#0< i < len -1
while i<len(l)-1:
    i+=1
    if l[i-1]<=l[i]:        
        s.append(l[i])
        lp+=l[i]-l[i-1]
        mp+=l[i]-l[i-1]     
    else:
        ser.append((lp,s))  
        s=[l[i]]        
        lp=0
    
    print ('i=%d l[i]=%d lp=%d mp=%d' %(i,l[i],lp, mp))

#i=len-1
ser.append((lp,s))       
print ('i=%d l[i]=%d lp=%d mp=%d' %(i,l[i],lp, mp))
print(ser) #list of buys series with local profits

def maxProfit(arr):
    ''' Return an array of (buy_day, sell_day) tuples that maximize profit '''
    if len(arr) == 0 or len(arr) == 1:
        return []

    l = []
    p = 0
    q = 1
    in_position = False

    while True:
        if arr[q]>arr[q-1]:
            if in_position:
                q+=1
            else:
                in_position = True
                q+=1

        else:
            if in_position:
                in_position = False
                l += [(p,q-1)]

            p = q
            q += 1

        if q == len(arr):
            if in_position:
                l += [(p,q-1)]
                in_position = False

            break

    return l

def maxProfit(arr):
    ''' Return an array of (buy_day, sell_day) tuples that maximize profit '''
    if len(arr) == 0 or len(arr) == 1:
        return []

    l = []
    p = 0
    q = 1
    in_position = False

    while True:
        if arr[q]>arr[q-1]:
            if in_position:
                q+=1
            else:
                in_position = True
                q+=1

        else:
            if in_position:
                in_position = False
                l += [(p,q-1)]

            p = q
            q += 1

        if q == len(arr):
            if in_position:
                l += [(p,q-1)]
                in_position = False

            break

    return l

The level of skill on this website is pathetic compared to websites like leetcode...

public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
int res = 0;
for (int i = 1; i < prices.length; i ++) {
res += Math.max(prices[i] - prices[i - 1], 0);
}
return res;
}

Ynkk

public class FindBestStockTransaction {
	static class Result {
		public Result(List<Integer> transactions, int sum) {
			this.transactions = transactions;
			this.sum = sum;
		}

		public Result(int startPrice, int endPrice, int sum) {
			this.transactions = new LinkedList<Integer>();
			this.transactions.add(startPrice);
			this.transactions.add(endPrice);
			this.sum = sum;
		}

		List<Integer> transactions;
		int sum;

		@Override
		public String toString() {
			return "Result [transactions=" + transactions + ", sum=" + sum + "]";
		}

	}

	static public Result find(int[] prices, int start) {
		if (prices == null || prices.length - start < 2) {
			return null;
		}
		if (prices.length - start == 2) {
			if (prices[start] >= prices[start + 1]) {
				return null;
			}
			return new Result(prices[start], prices[start + 1], prices[start + 1] - prices[start]);
		}
		Result bestResult = null;
		for (int end = start; end < prices.length; end++) {
			Result firstResult = null;
			if (end > start && prices[end] > prices[start]) {
				firstResult = new Result(prices[start], prices[end], prices[end] - prices[start]);
			}
			Result nextResult = find(prices, end + 1);
			Result newResult = combineResults(firstResult, nextResult);
			if (bestResult == null || newResult != null && bestResult.sum < newResult.sum) {
				bestResult = newResult;
			}
		}
		return bestResult;
	}

	private static Result combineResults(Result result1, Result result2) {
		if (result1 == null && result2 == null) {
			return null;
		}
		if (result1 == null) {
			return result2;
		}
		if (result2 == null) {
			return result1;
		}
		result2.transactions.add(0, result1.transactions.get(0));
		result2.transactions.add(1, result1.transactions.get(1));
		return new Result(result2.transactions, result1.sum + result2.sum);
	}
}