This problem seems to be finding the maxdiff in an array.
int maxdiff ( int A[], int n ) {
// write your code here
int max_diff = A[1] - A[0];
int min_element = A[0];
int i;
for(i = 1; i < n; i++)
{
if(A[i] - min_element > max_diff)
max_diff = A[i] - min_element;
if(A[i] < min_element)
min_element = A[i];
}
if(max_diff < 0)
max_diff = 0;
return max_diff;
}
.........
Satya
On Sat, Jun 12, 2010 at 3:18 PM, divya jain <[email protected]>wrote:
> i think we need to maintain an array of index as well such that while
> subtracting smallest element from largest element of sorted array we need to
> check if index of largest is greater than index of smallest. if no..then
> this is not the solution..
>
>
> On 12 June 2010 14:20, Modeling Expert <[email protected]>wrote:
>
>> Let's say array A , 1 till n
>>
>> s_index = 1; e_index = n ;
>> start = &A[s_index] ;
>> end = &A[e_index];
>> result = 0; //! j - i
>> if ( *end > *start ){
>> result = index(end) - index(start) ( only of its greater than
>> previous value of result )
>> break ;
>> }else{
>> end-- ; //! till you reach start
>> }
>>
>> now increment start , and repeat the process but only from A[n] till
>> A[++result] , going further
>> down is not required now.
>>
>> Average time < o(n^2)
>>
>> Worst case : let's say we have descending array of ints, theno(n^2)
>>
>> Please suggest improvements
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> On Jun 12, 12:14 am, amit <[email protected]> wrote:
>> > given an array A of n elements.
>> > for indexes j , i such that j>i
>> > maximize( j - i )
>> > such that A[j] - A [ i ]> 0 .
>> >
>> > Any Algorithm less than O(n^2) would do.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
