Algo:
a) Take first element as min; max = 0; sum = -1
b) for i in 1 to array[array.length-1]
if a[i] - min > 0 && a[i] - min > sum:
update max & sum;
else:
update min
c) if sum ! = -1, print max,min,max-min
else, no such combination a[i] - a[j] > 0, where i>j has been found.
Complexity: o(n)
Java code follows:
public class test {
public static void main(String args[]){
int[] a = {-10,13,-12,12,-5,-6,11};
int maxx,minn,sum;
maxx = 0;
minn=a[0];
sum=-1; // sum is supposed tobe +ve
for (int i =1; i <a.length;i++){
if ((a[i] - minn > 0) && (a[i] - minn > sum) ) {
maxx = a[i];
sum = a[i] - minn;
}
else {
if ( a[i] < minn) {
minn = a[i];
}
}
}
if (sum !=-1) {
System.out.println("Max a[i] is (i>j)"+maxx);
System.out.println("Min a[j] is (i>j)"+minn);
System.out.println("Max +ve diff is "+(maxx-minn));
}
else {
System.out.println("No combination a[i]-a[j] > 0 where i>j is found");
}
}
}
------------------------------------------------------------
On Mon, Jun 21, 2010 at 5: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.
>
>
--
cheers
Jeeva
--
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.
