Divide and Conquer to find maximum difference in an array

maximum difference in an array java hackerrank
maximum difference in an array hackerrank github
maximum difference in an array javascript
maximum difference in a matrix
divide and conquer algorithm to find maximum
max difference you can get from changing an integer
max difference between elements
finding maximum and minimum using divide and conquer in c

I am trying to solve a problem where given an array I need to calculate the maximum difference such that the larger element appears after the smaller element.

Here is a better problem statement:

Given the stock prices on each day for n days, what is the maximum profit a person can make by doing exactly one transaction. One transaction means that the person can buy exactly one stock on one day and sell it on a later date.

I am trying to solve this problem using divide and conquer algo.

In my recursive function i am trying to spilt the array into two halves, but i am not sure on how to proceed with logic. Do i just get the max difference in each halves and compare?

int calculateMaxDiff(int *src, int start, int end){
    if(end - start == 1) return src[start];

    int middle = (start + end)/ 2;
    int half1_diff;
    int half2_diff;
    half1_diff = calculateMaxDiff(src, start, middle);
    half2_diff = calculateMaxDiff(src, middle, end);

    //Do i need to have two loops here that calculate the diffs for each halves
    .... 
    return max(half1_diff, half2_diff);
 }

Edit: Example output

Give an array {12, 9, 18, 3, 7, 11, 6, 15, 6, 1 ,10} should return 12 as a result of difference between 15 and 3

The question in your problem can be translated into a better problem statement:

Given the stock prices on each day for n days, what is the maximum profit a person can make by doing exactly one transaction. One transaction means that the person can buy exactly one stock on one day and sell it on a later date.

The divide-and-conquer solution: Let's see if we can solve this by splitting the input in half, solving the problem in each subarray, then combining the two together. Turns out we actually can do this, and can do so efficiently! The intuition is as follows. If we have a single day, the best option is to buy on that day and then sell it back on the same day for no profit. Otherwise, split the array into two halves. If we think about what the optimal answer might be, it must be in one of three places:

  1. The correct buy/sell pair occurs completely within the first half.
  2. The correct buy/sell pair occurs completely within the second half.
  3. The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.

We can get the values for (1) and (2) by recursively invoking our algorithm on the first and second halves. For option (3), the way to make the highest profit would be to buy at the lowest point in the first half and sell in the greatest point in the second half. We can find the minimum and maximum values in the two halves by just doing a simple linear scan over the input and finding the two values. This then gives us an algorithm with the following recurrence:

T(n) = 2T(n/2) + O(n)

T(n) = O(nlogn)

Here is a simple implementation in Python. Its very simple to understand and its also easy to convert to C++:

def DivideAndConquerSingleSellProfit(arr):
    # Base case: If the array has zero or one elements in it, the maximum
    # profit is 0.
    if len(arr) <= 1:
        return 0;

    # Cut the array into two roughly equal pieces.
    left  = arr[ : len(arr) / 2]
    right = arr[len(arr) / 2 : ]

    # Find the values for buying and selling purely in the left or purely in
    # the right.
    leftBest  = DivideAndConquerSingleSellProfit(left)
    rightBest = DivideAndConquerSingleSellProfit(right)

    # Compute the best profit for buying in the left and selling in the right.
    crossBest = max(right) - min(left)

    # Return the best of the three
    return max(leftBest, rightBest, crossBest)

Edit: Here is the C++ implementation for the above algorithm

#include <iostream>
#include <algorithm>
using namespace std;
int calculateMin(int a[], int low, int high)
{
    int i,mini;
    mini = a[low];
    for(i=low;i<=high;i++)
    {
        if(a[i]<mini)
        {
            mini = a[i];
        }
    }
    return mini;
}
int calculateMax(int a[], int low, int high)
{
    int i,maxi;
    maxi = a[low];
    for(i=low;i<=high;i++)
    {
        if(a[i]>maxi)
        {
            maxi = a[i];
        }
    }
    return maxi;
}
int calculateMaxDiff(int a[], int low, int high)
{
    if(low>=high)
        return 0;

    int mid = (low+high)/2;
    int leftPartition = calculateMaxDiff(a,low,mid);
    int rightPartition = calculateMaxDiff(a,mid+1,high);
    int left = calculateMin(a,low,mid); // calculate the min value in the left partition
    int right = calculateMax(a,mid+1,high); // calculate the max value in the right partition
    return max(max(leftPartition, rightPartition), (right - left));

}
int main() {
    int arr[] = {12, 9, 18, 3, 7, 11, 6, 15, 6, 1 ,10};
    int len = sizeof(arr)/sizeof(arr[0]);
    int ans = calculateMaxDiff(arr, 0, len-1);
    cout << "Maximum Profit: " <<ans<<endl;
    return 0;
}

Hope it helps!!!

Maximum difference between two elements such that larger element , Given an array arr[] of integers, find out the maximum difference between any two elements Duration: 11:18 Posted: 10 Sep 2011 Using Divide and Conquer approach, we can find the maximum subarray sum in O (nLogn) time. Following is the Divide and Conquer algorithm. 1) Divide the given array in two halves. 2) Return the maximum of following three. …. a) Maximum subarray sum in left half (Make a recursive call) ….

There is no need in complicated D/C algorithm because simple cycle with checking like

 maxdiff = max(current - min_so_far, maxdiff)
 update min_so_far

solves the problem

If you really want to apply divide and conquer method, you may return triplet {local_min, local_max, local_max_diff} from recursive function like:

left = calculateMaxDiff(start, middle)
right = calculateMaxDiff(middle + 1, end)
return {min(left.local_min, right.local_min), 
        max(left.local_max, right.local_max), 
        max(left.local_diff, right.local_diff, right.localmax - left.local_min)

Maximum difference between two elements in an Array , Given an array arr[] of N integers, the task is to find the maximum difference between any two elements of the array. Examples: Input: arr[] = {2, 1, 5, 3} Output: 4 The maximum element in the array is 9 We can easily solve this problem by using Divide and conquer (D&C). The idea is to recursively divide the array into two equal parts and update the maximum and minimum of the whole array in recursion itself by passing minimum and maximum variables by reference.

The key for a divide and conquer algorithm is the conquer part.

For this problem the most important condition is:

the larger element appears after the smaller element

For an array src, after dividing src to 2 halves, half1 and half2, suppose the answer would be in position i and j, there are 3 cases now:

  1. i and j are both in half1 -> half1_diff
  2. i and j are both in half2 -> half2_diff
  3. i is in half1 and j is in half2

So the main part is to deal with case3. As the larger one comes after, so we just need to find the minimum value min_half1 in half1 and the maximum value max_half2 in half2, and check if it meets the condition max_half2 >= min_half1 and update the result as max(half1_diff, half2_diff, max_half2-min_half1).

In order to calculate min_half1 and max_half2 efficiently, you have to keep the record of min and max value of the array, and it takes O(1) time.

So T(n) = 2T(n/2) + O(1), T(n) = O(n).


Check the example for more details

http://ideone.com/TbIL2r

Maximum difference between two elements where larger element , Given an array A[], write an algorithm to find Maximum difference between Divide and Conquer Index i is in left half and index j is in right half of the array. Coding Up Maximum Subarray Sum Using Divide and Conquer As we know that the divide and conquer solves a problem by breaking into subproblems, so let's first break an array into two parts. Now, the subarray with maximum sum can either lie entirely in the left subarray or entirely in the right subarray or in a subarray consisting both i.e

Algorithm, 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[]. Max  C program to find maximum and minimum of an array using Divide & Conquer rule Today I am going to post a program that is going to find out the maximum and minimum element of an array. You will say that it is very easy.

What is the difference between elements?, How do you find the minimum difference in an array? Another way to do this could be by following the divide and conquer strategy. Just like the merge sort, we could divide the array into two equal parts and recursively find the maximum and minimum of those parts. After this, compare the maximum and minimum of those parts to get the maximum and minimum of the whole array.

Find Maximum distance between adjacent elements of an array , How do you find the distance between adjacent and array elements? The Max-Min Problem in algorithm analysis is finding the maximum and minimum value in an array. Solution. To find the maximum and minimum numbers in a given array numbers[] of size n, the following algorithm can be used. First we are representing the naive method and then we will present divide and conquer approach. Naïve Method. Naïve method is a basic method to solve any problem. In this method, the maximum and minimum number can be found separately.

Comments
  • What is this even trying to achieve? Do you have sample usage cases and expected results?
  • @tadman i added an example output
  • So you need to compute the maximum and minimum values for your whole array. There's no need for recursion here, just two variables and a single iteration loop. In fact, I don't think you can (efficiently) solve this with recursion.
  • yes i know but i am trying to achieve this using divide and conquer
  • I know what you're trying, but I think it's not just pointless but impossible with just one return value.
  • No offense, but I find it a little excessive to call this O(nlgn) algorithm "efficient" when a linear (and at least as simple) version exists ;)
  • Thanks @User_Targaryen for the breakdown
  • @PatriceGahide: The author was trying to implement the divide and conquer technique to this problem. That is why I provided the divide and conquer approach. Even I know that there is a simple linear solution to the problem!!!!
  • I understand perfectly, and this indeed answers the question beautifully. It's just that you say this O(nlgn) algorithm is "efficient", without even mentioning the fact that a simple traversal algorithm is asymptotically better than the solution you present here, or (and even more importantly) that D&C can also achieve linear-time complexity with just a few adjustments. Considering that, the word "efficient" seemed a little optimistic, that's all. No big deal.
  • it should be maxdiff = max(current - min_so_far, maxdiff)