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 <amitjaspal...@gmail.com> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
