Find maximum profit if you can buy & sell share just once.
Given an array of integers, find out the difference between any two elements such that larger element appears after the smaller number.
Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9).
This difference can be the largest profit if shares are allowed to buy and sell once.
so in simple words
we need to find A[i] and A[j] such that A[i] < A[j] and i< j
Think what can be done to achieve that.
[2, 3, 10, 6, 4, 8, 1] in this wee nedd to find 2 and 10.
[2, 3, 10, 1, 4, 8, 11] thn in this it should be 1 and 11.
so as we read array from index 0 to N, we can find max_number later.
but we need to keep track of minimum number.
We can keep track of
1) minimum number , min_num found so far
2) maximum difference, max_dif found so far.
now if for next element in array , current diff ( A [ j ] - min_num ) is larger than existing then update max diff.
and if A[ j ] is smaller then min_num update it.
code
#include<stdio.h>
int maxDiff(int a[], int length)
{
int max_diff = a[1] - a[0];
int min_element = a[0];
for( int i = 1 ; i < length ; i++ )
{
if(a[i] - min_num > max_diff)
max_diff = a[i] - min_num;
if(a[i] < min_num)
min_num = a[i];
}
return max_diff;
}
int main()
{
int a[] = {1, 2, 6, 80, 100};
int len = sizeof(a)/sizeof(a[0]);
printf("Maximum difference is %d", maxDiff(a, len));
return 0;
}
[…] you can just buy and sell once thenn? -> you can think for Max and Min such that index_Max > index_Min. so this code is extension of Max and Min such that index_Max > […]