ravigupta
BAN USERTraverse 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)
here you are assuming things .... what you are saying is correct for the case you are describing .... but given the problem statement ... hashing C would be better.... i can cross argue with your assumption that what about the case were C is of fixed length and A and B are infinite streams of integers.... So its totally depend upon the nature of arrays A, B and C.
- ravigupta May 21, 2012Use hashing: O(n) time and in single iteration - Take the first number from the array, subtract d from it and search the remaining number in the hash table, if found, we got a pair otherwise store the element a[i] in the hash table. Do this for all the elements in the array.
- ravigupta May 14, 2012
Segmentation Fault: dereferencing a NULL pointer
- ravigupta June 02, 2012