CareerCup

Hey, can you like redefine the term Maximum Loss. like what is the referral point to calculate loss. Thanks

Go thru the following article:
leetcode.com/2011/05/a-distance-maximizing-problem.html

Might help u ...

Traverse the array once keeping track of max_price_so_far and the max_loss_so_far

int max_loss(int price[], int n)
{
    int max_loss_so_far = 0;
    int max_price_so_far = price[0];

    int curr_loss=0;
    for (int i=1; i<n; i++)
    {
        curr_loss = max_price_so_far - price[i];
        if (curr_loss > max_loss_so_far)
            max_loss_so_far = curr_loss;
        if (price[i] > max_price_so_far)
            max_price_so_far = price[i];
    }

    return max_loss_so_far;
}

Time: O(n)
Space: O(1)

the question can be rephrased as

find i and j such that a[i]-a[j] is maximum and i>j...now this can be solved in O(n)

int n=10,min=arr[0],max=-32767	;
	for(int i=1;i<n;i++)
	{
		if(arr[i]<min)
		{
			min=arr[i];
			continue;
		}
		if(arr[i]-min>max)
			max=arr[i]-min;
	}
	cout<<"MAX DIFFERENCE IS : "<<max;

define f(n) is the max price before price n,
just find max(f(n)-price(n)) that's the max lose

public static int getMaximumDifference (int [] array){
int max = 0;
int min = array[0];
for(int i=0;i<array.length;i++){
if(array[i]>max) max = array[i];
if(array[i]<min) min = array[i];
}
System.out.println(max);
System.out.println(min);
int diff = max - min;
return diff;
}

public static void main(String [] args){
int [] arr = {6,7,3,2,5,6,79,2,35,67,8,9,999,67};
System.out.println(getMaximumDifference(arr));
}

Take the difference of ech day, and make array.change the sign of each elemnt in array.Then use Longest Maximum subarray solution(Kadane algor

traverse the array by checking each day price change. If it is negative this is a lost so we sum to the result. Otherwise we do not. Here is the Java code:

public int maxLoss(int[] a) {
  int result = 0;
  
  for (int i = 1; i <  a.length; i++)
   result += Math.min(0, a[i] - a[i - 1]); 
 
  return result;
 }

if(price(i) > currentMax){
currentMax = price(i)
}
else{
currentloss = currentMax-price(i);
if(currentloss > maxloss){
maxloss = currentloss;
}

tree

One fool proof way is to quick sort the array(complexity of logn) and find the diff of first and last elements.

In one traversal, we can find which is the smallest and which is the largest.
Diff of them could give our answer.

Dear
Prices are increasing day by day, it means sorted form so just do it very simple like..

maxLoss = price[n]-price[1];
:-)

Dear
Prices are increasing day by day, it means sorted form so just do it very simple like..

maxLoss = price[n]-price[1];
:-)