CareerCup

correct me if i wrong:

max = a[0]; loss = 0;
for(int i = 1; i < n; i++) {
    if(a[i] >= max) {
        max = a[i];
    } else {
        loss = max(loss, max - a[i]);
    }
}

Start from right end. For each number save in another array the number which is smallest number that falls to right of it. Call this the min array.Can be done in O(n).
Now start from beginning and initialize loss to 0.Now for each number find the difference between the number and corresponding index in the min array and if its greater than loss, make it the new loss. Report loss after the end of loop. This step should take O(n) time. Total time complexity = O(n) and space complexity = O(n).

#include<iostream>

using namespace std;
int MaxLossInStockPrice(int inputArray[], int length)
{
	int maxLoss = 0;
	for(int i = 0; i < length; i++)
		for(int j = i; j < length; j++)
		{
			if(inputArray[i] - inputArray[j] > maxLoss)
			{
				maxLoss = inputArray[i] - inputArray[j];
			}
		}
	return maxLoss;
}

int main()
{
	int a[] = {1,2,3,7,5,8,9,4,6,10,12};
	int length = sizeof(a)/sizeof(*a);
	cout<<MaxLossInStockPrice(a, length);
}

<pre lang="" line="1" title="CodeMonkey1145" class="run-this">void getMaxPrice(int *arr, int nLength)
{
if (NULL == arr)
return;

for (int i = nLength-1;i > 0;i--)
arr[i] = arr[i-1] - arr[i];

int maxp = 1, minp = 1, maxValue = arr[1];
int maxtmp = 1, mintmp = 1, tmpValue = arr[1];
for (int i = 2;i < nLength;i++)
{
if ((tmpValue + arr[i]) > arr[i])
{
mintmp = i;
tmpValue += arr[i];
}
else
{
mintmp = maxtmp = i;
tmpValue = arr[i];
}

if (tmpValue > maxValue)
{
maxValue = tmpValue;
maxp = maxtmp;
minp = mintmp;
}
}

for (int i = 1;i < nLength;i++)
arr[i] = arr[i-1] - arr[i];
printf("%d - %d = %d\n",arr[maxp-1],arr[minp],maxValue);
return ;
}
</pre><pre title="CodeMonkey1145" input="yes">
</pre>

int maxLoss(int a[],int n)
{
    int max=a[0],maxloss=0;
    for(int i=1;i<n;i++)
    {
            if(maxloss<max-a[i])
            maxloss=max-a[i];
            if(max<a[i])
            max=a[i];
    }
    return maxloss;

}

Maxloss(i) = max(MaxLoss(i-1), (maxValTillNow - a[i]))

Base Case
if(i == 1)
  return a[0]-a[1]

Complexity O(n)

solution 1 is wrong

<pre lang="" line="1" title="CodeMonkey98658" class="run-this">class MaxLoss {
public int maxLoss(int[] prices) {
int maxLoss = 0;
for(int i = 0; i < prices.length; ++i) {
int curMaxLoss = 0;
for(int j = i + 1; j < prices.length; ++j) {
if(prices[i] > prices[j]) {
curMaxLoss = Math.max(curMaxLoss, prices[i] - prices[j]);
}
}
maxLoss = Math.max(maxLoss, curMaxLoss);
}
return maxLoss;
}

public static void main(String[] args) {
int[] prices = {1, 2, 3, 7, 5, 8, 9, 4, 6, 10, 12 };
System.out.println(new MaxLoss().maxLoss(prices));
}
}
</pre><pre title="CodeMonkey98658" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey65891" class="run-this">class MaxLoss {
public int maxLoss(int[] prices) {
int maxLoss = 0;
for(int i = 0; i < prices.length; ++i) {
for(int j = i + 1; j < prices.length; ++j) {
if(prices[i] > prices[j]) {
maxLoss = Math.max(maxLoss, prices[i] - prices[j]);
}
}
}
return maxLoss;
}

public static void main(String[] args) {
int[] prices = {1, 2, 3, 7, 5, 8, 9, 4, 6, 10, 12 };
System.out.println(new MaxLoss().maxLoss(prices));
}
}
</pre><pre title="CodeMonkey65891" input="yes">
</pre>

static int findMaxLoss(int array[]){
		int max = array[0];
		int res = -1;
		for (int i = 1; i < array.length; i++) {
			if(array[i] - max < 0)
				res = Math.max(res, max = array[i]);
			max = Math.max(max, array[i]);
		}
		return res;
	}