Divide and Conquer Algo to find maximum difference between two ordered elements

Posted by instance on Stack Overflow See other posts from Stack Overflow or by instance
Published on 2014-06-05T08:47:40Z Indexed on 2014/06/05 9:26 UTC
Read the original article Hit count: 226

Filed under:

algorithm

|

divide-and-conquer

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].

Examples:

If array is [2, 3, 10, 6, 4, 8, 1, 7] then returned value should be 8 (Diff between 10 and 2).
If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)

My Algorithm:

I thought of using D&C algorithm. Explanation

2, 3, 10, 6, 4, 8, 1, 7

then

2,3,10,6      and     4,8,1,7

then

2,3  and 10,6  and  4,8 and 1,7

then

2 and 3   10 and 6   4 and 8    1 and 7

Here as these elements will remain in same order, i will get the maximum difference, here it's 6.

Now i will move back to merege these arrays and again find the difference between minimum of first block and maximum of second block and keep doing this till end.

I am not able to implement this in my code. can anyone please provide a pseudo code for this?

© Stack Overflow or respective owner

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More

Related posts about divide-and-conquer

nth smallest number among two databases of size n each using divide and conquer

as seen on Stack Overflow - Search for 'Stack Overflow'
we have two databases of size n containing numbers without repeats. So, in total we have 2n elements. They can be accessed through a query to one database at a time. The query is such that you give it a k and it returns kth smallest entry in that database. we need to find nth smallest entry among… >>> More
Divide and conquer method to compute roots

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Knowing that we can use Divide-and-Conquer algorithm to compute large exponents, for exemple 2 exp 100 = 2 exp(50) * 2 exp(50), which is quite more efficient, is this method efficient using roots ? For exemple 2 exp (1/100) = (2 exp(1/50)) exp(1/50) ? >>> More
Divide and conquer method to compute roots [SOLVED]

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Knowing that we can use Divide-and-Conquer algorithm to compute large exponents, for exemple 2 exp 100 = 2 exp(50) * 2 exp(50), which is quite more efficient, is this method efficient using roots ? For exemple 2 exp (1/100) = (2 exp(1/50)) exp(1/50) ? In other words, I'm wondering if (n exp(1/x))… >>> More
Divide and conquer of large objects for GC performance

as seen on Stack Overflow - Search for 'Stack Overflow'
At my work we're discussing different approaches to cleaning up a large amount of managed ~50-100MB memory.There are two approaches on the table (read: two senior devs can't agree) and not having the experience the rest of the team is unsure of what approach is more desirable, performance or maintainability… >>> More
Rails : fighting long http response times with ajax. Is it a good idea? Please, help with implementa

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, everybody! I've googled some tutorials, browsed some SO answers, and was unable to find a recipe for my problem. I'm writing a web site which is supposed to display almost realtime stock chart. Data is stored in constantly updating MySQL database, I wrote a find_by_sql query code which fetches… >>> More