Design an algorithm to find the best times to buy and sell the sock to maximize the benifit

Some times back A guy From Chennai Named praveen send me this interesting problem. but some one recently send me mail for the same to solve it efficiently so thought to posting it.problem is really interesting and if after epending soem time with problem someone can come with efficient solution then its really fun isn't it :) In first look problem is not easy although i am sure most of geeks would already have done the same problem efficiently but in direct way that i will show below how we can transform this probelm into simple array probelm.

Problem Statement

You have an array for which the ith element is the price of a given stock on day i.If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.
or to maximize the benefit ?

Problem Solving Approach

The very first think that comes to mind is that finding the minimum and maximum value would do, but it does have a hidden restriction, that is:

Contraint: You must buy before you can sell. ohhh No i need some more info or i have to trick :)

Hint: Find i and j that maximizes Aj - Ai, where i <= j. There is an obvious O(N2) solution, Algorithm for this Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far.outer loop will run for the buy price/day & innner loop will run for seling price/day . #include

int MaximumBenefit(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int buy, sell;
for(buy = 0; buy < arr_size; i++) { for(sell= buy +1; sell< arr_size; j++) { if(arr[sell] - arr[buy] > max_diff)
max_diff = arr[sell] - arr[buy];
}
}
return max_diff;
}

int main()
{
int arr[] = {2, 3, 10, 6, 4, 8, 1};
printf("Maximum difference is %d", MaximumBenefit(arr, 7));
getchar();
return 0;
}

Time Complexity: O(n^2)
Time Complexity: O(1)

Can't we reduce the time compelxity yes in fact we can do better in just
O(N).And ofcourse this the hidden part of problem but this how computer science can applied to real life probelms to slove it efficiently & get maximum benefits isn't it ? Now i can say if you will do some twaek with your mind , you will able to come up with nice O(N) linear tiem solution :) start thinking whats the main think we requirs to solve it ? what we have to maximiz e? whats the contrint ?

Algorithm is simple
In this method, instead of taking difference of the buying price with every other selling price , we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far (max_diff).
2) Minimum number visited so far (min_element). thats starting such index from oth location that has minimum value

so as said aobve to solve this problem efficiently, you would need to track the minimum value's index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

int MaximumBenefit(int stocksprice[], int size)
{
int min = 0;
int maxDiff = 0;
int buy=0,sell=0;
for (int i = 0; i < size; i++) { if (stocksprice[i] < stocksprice[min]) min = i; int diff = stocksprice[i] - stocksprice[min]; if (diff > maxDiff)
{
buy = min;
sell = i;
maxDiff = diff;
}
}
return maxDiff;
}


Time Complexity O(N)
Space Complexity O(1)
Run Here https://ideone.com/L1VEf