using divide and conquer you can do it in O(nlogn) your recursive function
must return three values the max and min value in this range and the maximum
difference
but this can also be solved in O(n)
start from the end of array if you loop backward you can determine the
max(a[i]) for i>=j
and then subtract it from a[ j ]
S=0;
Max = a[n-1];
for ( j=n-2 ; j>=0 ; j-- ){
if (Max - a[j] > S)
S=Max - a[j];
if ( a[j] > Max )
Max = a[j];
}
On Mon, Jun 21, 2010 at 4:38 PM, amit <[email protected]> wrote:
> There is an integer array consisting positive and negative integers.
> Find maximum positive difference S defined as:
>
> S = a[i] - a[j] where i>j
> and
> S > 0
>
> --
> 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.
