CareerCup

What abt creating a profit[i] = ar[i+1]-ar[i]..

The problem now is to find the subsequence with maximum sum!!

//Solution in o(n) time:

void stock_profit(int a[])
{
int i,j;
int time1, time2, sum, max_sum;
j=sum=max_sum=0;
for(i=1; i<SIZE; i++)
{
if(a[j] >= a[i])
{

sum = 0;
j=i;
}
else
{
if((a[i] - a[j]) > sum)
{
sum = a[i] - a[j];
if(max_sum < sum)
{
max_sum = sum;
time1 = j;
time2 = i;
}
}
}
}

printf("Maximum Profit in between interval %d and %d", time1, time2);
}

maxProfit = 0
for i 0 to n
{
 minHeap.insert(a[i])
 
 if a[i] - minHeap.Minimum > maxProfit {
  buy = minHeap.Minimum
  sell = a[i]
 } 
}
return sell - buy;

I think a divide-and-conquer approach works here like merge-sort. We recursively divide the range in half:
1) divide steps:
[i] 'buy' and 'sell' lies in 1st half
[ii]'buy' and 'sell' lies in 2nd half
2) merge: 'buy' lies in 1st half and and 'sell' lies in 2nd half -> this takes O(1) time because 'buy' price is the leftmost one in 1st half, and 'sell' price is the rightmost. However, to merge two sorted list, it'll be O(n).

So time complexity is O(nlog n). Plz comment if seems this doesn't work for every input.

An example to support my approach:

3 8 5 1 7 18 16 4
sublist[3,8] => min=3,max=8,profit=5
sublist[5,1] => min=1,max=5,profit=-4
merge [3,8,5,1] => min=1,max=8, profit = MAX {5,-4, (5-3)} = 5

sublist[7,18] => min=7,max=18,profit=11
sublist[16,4] => min=4,max=16,profit=-12
merge [7,18,16,4] => min=4,max=18, profit = MAX {11,-12, (16-7)} = 11

final merge[3,8,5,1,7,18,16,4] => profit = MAX {5, 11, (18-1)} = 17

So it is an O(n) solution, lowest bound for this problem. Plz comment on any catches in this method.

@buried
What is we use dynamic programming using recursion like this:
1. divide given array in left and right subarray
2. buy defined as - minimum of left. sell defined as - maximum of right.
3. find minimum of left and maximum of right. Subtract and get the profit and corresponding buy/sell values stored.
4. Further divide both left and right subarrays and repeat step 3 in each of them. If the profit derived is less than current maximum profit in any of the new sub arrays we don't consider it further.

Example:
3 8 5 1 7 18 4

First Recursion:
Left - 3 8 5
Right - 1 7 18 4
P1 = max (Right) - min (Left) = 18 - 3 = 15.

Second Recursion:
LeftLeft - 3
LeftRight - 8 5
P2 = 8 - 3 = 5 (less than P1 don't consider this further)

RightLeft - 1 7
RightRight - 18 4
P3 = 18 - 1 = 17 (greater than P1, we will do more recursion but won't get the max).

Let me know.

Is'nt this same as finding max(A[j]-A[i]) with j>i . I think this can be done in O(n).

To represent it correctly its Max(A[i+1]-Minof(A[i]-- i ranges from 1 to i). First we can calculate all the values Minof(A[i]--i ranges from 1 to i) . Then we can subtract calculated values from A[i+1] and find Max among them

int stock[] = {3,8,5,1,7,18,4};
int curMax = 18;
int curMin = stock[0];
int curMaxDiff = curMax-curMin;
for (int i = 0; i<7;i++) {
if (stock[i] < curMin) {
curMin = stock[i];
} else if ((stock[i] - curMin) > curMaxDiff) {
curMaxDiff = stock[i] - curMin;
}
}
std::cout << curMaxDiff <<std::endl;
}

public class Puzzle {
public static void main(String[] args){
int[] a = {3,8,5,1,7,18,4};

int max = 0;

int diff = 0;

for(int i=0; i<a.length-1; i++){
for(int j=i+1; j<a.length; j++){
diff = a[j] - a[i];
max = max > diff ? max : diff;
}
}

System.out.println(max);
}
}

Complexity = O(n * (n-1)) = O(n square)

Here is a solution which takes O(n) in time and O(n) in space.

Go through the array P=(p1,p2,p3,...pn), in reverse and build another array M (max), which has the maximum so far. M=(m1,m2,,3...mn), where mk is the maximum from position k to the end of the array (i.e. mn is pn, m(n-1) is the max between pn and p(n-1)...m3 is the max from p3 to pn. Recursively mk=max(mk+1,pk), and thus traversing the array P backwards constructs M in a single traversal O(n).

Now, go through the array P again, and for each value pk, compute profit=mk-pk. Find the maximum profit. Done.

class Deal
{
	public int startID, endID, startValue, endValue, deal;
	
	public Deal(int startID, int endID, int startValue, int endValue, int deal)
	{
		this.startID = startID;
		this.endID = endID;
		this.startValue = startValue;
		this.endValue = endValue;
		this.deal = deal;
	}
}

public class Test {
	public static void main(String []args)
	{
		int arr[] = new int[] {3,8,5,1,7,18,4};
		bestDeal(arr);
	}
	
	public static void bestDeal(int arr[])
	{
		Deal res[] = new Deal[arr.length];
		int min = Integer.MAX_VALUE, minID = 0, deal = 0;
		
		for(int i = 0; i < arr.length; i++)
		{
			if(arr[i] >= 0 && arr[i] <= min)
			{
				min = arr[i];
				minID = i;
			}
			
			res[deal++] = new Deal(minID, i, min, arr[i], arr[i] - min);
		}
		
		for(Deal x : res)
			System.out.println(x.startID + " " + x.startValue + " " + x.endID + " " + x.endValue + " " + x.deal);
	}

}

int MaxStockGain(int arr[], int size)
> {
>     if(size <= 0)
>         return 0;
>
>     int curMin = arr[0];
>     int MaxGain = 0;
>
>     for(int i = 1; i < size; ++i)
>     {
>         if (arr[i] < curMin)
>         {
>             curMin = arr[i];
>
>         }
>
>
>         int currGain = arr[i] - curMin;
>         if(currGain > MaxGain)
>         {
>             MaxGain = currGain;
>         }
>     }
>
>     return MaxGain;

here is what I thought... Traverse whole array and find minimum value...

After min value is found then traverse again and find the max value starting from the index where the min value was found. This will give you min value to buy and maxvalue to sell for particular stock.

Time Complexity O(n)
Space complexity O(1)

Take 2 pointers, point first at the start and second to the last of the array of price interval.
Move both the pointers till they collide.
-move first to forward direction to find the least price & store its position. 
-move second to backward direction to find highest price & store its position.

Now the profit is highest-lowest