CareerCup

If next day price > today's price and no stock in possession => buy
else if next day price < today's price and stock in possession => sell

void maxProfit(int prices[], int len) {
        int i;
        int buy = -1;
        
        for( i = 0; i < len-1; i++ ) {
            if( buy == -1 && prices[i] < prices[i+1] ) {
                buy = i;
                printf( "Buy on day %d\n", i );
            } else if( buy != -1 && prices[i] > prices[i+1] ) {
                profit += prices[i]-prices[buy];
                buy = -1;
                printf("Sell on day %d\n", i );
            }
        }
        
        if( buy != -1 ) {
            profit += prices[len-1]-prices[buy];
            printf("Sell on day %d\n", i );
        }
        
       // profit = max profit acquired
    }

Alternatively, it can solved by finding all disjoint longest increasing subarrays. This can be done in O(n). Buy on first element of subarray and sell on last element of subarray for each of these subarrays.

e.g. 2 1 3 6 8 2 4 1 9
Longest increasing disjoint subarrays are { 1, 3, 6, 8 }, { 2,4 }, { 1,9 }
Buy at 1 - sell at 8
Buy at 2 - sell at 4
Buy at 1 - sell at 9

Buy Low, Sell High:

Basically, you want to buy a share if you have no shares and you know the next day the stock will trade higher, because you're at a local minimum. You want to sell a share if you have a share and you know the next day the stock will trade lower, because you're at a local maximum. Iterate through the array in O(N) time to figure out when you buy and sell. Don't buy stock on the last day for obvious reasons.

The more common variation of this problem is actually harder. Suppose you're only ever allowed to make one purchase. It would possibly be a short sighted strategy to buy at a local minimum, because you would be forgoing a future buying opportunity at an even lower price. But if you're allowed multiple buy/sell opportunities, this isn't an issue, because you can collect earning after every increase.

Buy at local minima, sell at local maxima

1) Find the gradient of stock price with respect to days. ie, tomorrows stock price - todays stock price.
2) We buy or sell only when the gradient moves to either side of zero.
   2.a) Buy stock on the day when tomorrows price - todays price moves from -ve value (or zero) to +ve value
   2.b) Sell the stock on the day when tomorrows price - todays price moves from +ve value (or zero) to -ve value

O(n)

private static int findMaxProfit(int[] arr)
{

int min = arr[0];
int max = arr[0];
int maxProfit = max - min;

for(int i = 0; i < arr.length; i++)
{
if(arr[i] < min)
{
min = arr[i];
max = arr[i];
}

if(arr[i] > max)
{
max = arr[i];
}

if(maxProfit < max - min)
{
maxProfit = max - min;
}
}


return maxProfit;
}

int ComputeBest(int *p, size_t n)
{
    int *B = new int[n + 1];
    int *S = new int[n + 1];
    
    memcpy(B, 0x00, sizeof(int) * (n + 1));
    memcpy(S, 0x00, sizeof(int) * (n + 1));
    
    for(size_t index = n - 1; index >= 0; ++index)
    {
        B[i] = max( B[i+1], -p[i] + S[i+1] );
        S[i] = max( S[i+1], -p[i] + B[i+1] );
    }
    
    return B[0];
}

I don't understand this problem clearly. But I think it can be solved like this:
For price array A: [3 7 4 10 11 8 5 4 8]
We get the difference array B: [4 -3 6 1 -3 -3 -1 4]
So we just buy the share at the price of A[i] when B[i] > 0 and we have no share in hand!
We sell the share at the price A[j] when B[j] < 0 and we have one share in hand.
At last if we have a share in hand, just sell it.
So the result is like this:[buy sell buy hold sell hold hold buy sell]

#include<stdio.h>
int main()
{
int i,buy=-1,profit=0;
int array[]={3,7,4,10,11,8,5,4,8,6};
for(i=0;i<9;i++)
{
if(buy==-1 && (array[i+1]-array[i])>0 )

{buy=array[i];
profit-=buy;
printf("bought day %d ",i+1);
}
else
if(buy!=-1 && (array[i+1]-array[i])<0)
{
profit+=array[i];
buy=-1;
printf("sell stoch day %d",i+1);
}
}

}

int maxprofit(int a[],int n)
{ int profit=0;
int min=a[0],max=a[0];
for(int i=0;i<n;i++)
{ if(a[i]<min) min=a[i];
if(a[i]>a[i+1])
{ profit+=a[i]-min; min=a[i+1];}
}
return profit;
}

The Algorithm is following

Let A[i=1 to N] is the daily stock price process and initally we don't own any stock.
    start = 1;
    while(start <= N)
      find first element such that next element is bigger then that. set it  buying price of stock.
      find first element such that next element is lesser then it. set it selling price.
      find profit and add it to sum and set new start to selling price element index + 1
 For Example : Here in this case we will have {3,7}, {4,11},{4,8} are the buying selling tuples, and net profit is 4 + 7 + 4 = 15.

This is the flow i can think of -
Buy on first day
if( arr[i] > arr[i-1] && arr[i+1<arr[i]
sell on i and compute the profit
if(arr[i] < arr[i+1]
Buy on i, compute profit
if(arr[i] > arr[i-1] && arr[i+1>arr[i])
Do not do anything

sell on last day. and compute profit

cleaned version of solution in C++

#include <iostream>
using namespace std;

void maxProfit(int prices[], int len) {
    int at_hand = 0;
    int profit = 0;
    cout << len << endl;
    for (int i=0; i <= len-1; i++) {
        if (at_hand == 0 && prices[i] < prices[i+1]) {
            at_hand = 1;
            cout << "Buy on day " << i+1 << endl;
        }
        else {
            if (at_hand != 0 && prices[i] > prices[i+1]) {
                profit += prices[i] - prices[i+1];
                cout << "Sell on day " << i+1 << endl;
                at_hand = 0;
            }
        }
    }
    cout << "Net profit = " << profit << endl;
}

int main() {
    int stock_prices[] = {5,4,7,4,3,6,8,4,3,6};
    int len = sizeof(stock_prices)/sizeof(int);
    maxProfit(stock_prices, len);
    return 0;
}

The problem becomes as follows:
Find all pairs of form (A,B), where B>A, such that the sum of the differences in the numbers of every pair is maximum and no two pairs must contain the same element from the given array.

Optimal Substructure:

F(i) = max{
			 A[i]- A[j] + F(j-1)  --> if A[i] > A[j]
		OR 	 F(j-1)		      --> otherwise
		} where 0<=j<=i;

Base Case:
F(-1) = F(0) = 0;

/*
Given a share's prize on each day in an array. Find an algo that will give the maximum profit.
The share can be either bought or sold on a day. Not both.
*/
#include <iostream>
#include <stdio.h>
#include <Math.h>

using namespace std;

//Without Dynamic Programming
int F(int A[], int end)
{
	// Base:
	if( end==-1 || end==0 ) return 0;

	int maxVal = 0;

	for( int i=0; i<=end; ++i)
	{
		maxVal = max( maxVal,
						(A[end]>A[i] ? (A[end] - A[i]) : 0) + 
						F(A, i-1));
	}

	return maxVal;
}

// With Dynamic Programming
int dpF(int A[], int end, int sol[])
{
	if (sol[end]>-1) return sol[end];

	int maxVal = 0;

	for( int i=0; i<=end; ++i)
	{
		maxVal = max( maxVal,
						( A[end]>A[i] ? (A[end] - A[i]) : 0 ) + 
						( (i>1) ? dpF(A, i-1, sol) : 0 ));
	}
	
	sol[end] = maxVal;
	return maxVal;
}

int main()
{
	int A[] = {3,10,4,6};
	int lenA = sizeof(A)/sizeof(A[0]);
	
	int sol[10];	// not more than 100 boards
	//					// and 10 painters
	memset(sol, -1, sizeof(sol[0]) * 10);
	//
	cout<<F(A, lenA-1)<<endl;
	cout<<dpF(A, lenA-1, sol)<<endl;
	
	// system("PAUSE");
	return 0;  
}

Time Complexity: O(n^3) for Dynamic Programming Solution

Maximum Sum SubArray problem