Maximum and Minimum using Divide and Conquer in Java

Posted By: Java Examples - 10:00 PM

Share

& Comment

Divide-and-Conquer Min-Max
As we are dealing with sub problems, we state each sub problem as computing minimum and maximum of a sub array A[p . . q]. Initially, p = 1 and q = A.length, but these values change as we recursive  through sub problems.To compute minimum and maximum of A[p . . q]: Divide by splitting into two sub arrays A[p . .r] and A[r+1 . . q], where r is the halfway point of A[p . . q]. Conquer by recursively computing minimum and maximum of the two sub arrays A[p . .r] and A[r+1 . . q]. Combine by computing the overall minimum as the min of the two recursively computed minimum, similar for the overall maximum.



Algorithm is Given bellow :
MaxMinPair dacMaxMin(int i, int j){
// Let a[0:n-1] be a global array.
int max , min ;
if (i == j) max = min = a[i]; // Small problem
   else if (i == j-1) { // Another case of small problem
       if (a[i] < a[j]){ max = a[j] ; min = a[i] ; }
       else { max = a[i] ; min = a[j] ; }
  }
    else{ 
/* If the problem is not small, divide it into subproblems.
Find where to split the set. */
    int mid=(i+j)/2;
    // Solve the subproblems.
    MaxMinPair p = dacMaxMin(i, mid);
    MaxMinPair p1 = dacMaxMin(mid+1, j);
    // Combine the solutions.
    if (p.max < p1.max) max = p1.max;
    else max = p.max;
    if (p.min > p1.min) min = p1.min;
    else min = p.min;
    }
 return new MaxMinPair(max,min);
}

Java version of the Max_Min is given below:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 *
package maxmin;
/**
 *
 * @author ACHCHUTHAN
 */
public class MaxMin {

    int[] array;
    int max, min;

    public MaxMin(int n) {
        //create array with size n
        array = new int[n];
        //asign random value into the array
        for (int i = 0; i < n; i++) {
            array[i] = (int) Math.round(Math.random() * 12 + 26);
        }
    }

    public int getMax() {
        return max;
    }

    public int getMin() {
        return min;
    }

    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "|");
        }
        System.out.println();
    }

    public void dacMaxMini() {
        dacMaxMin(0, array.length - 1);
    }

    public void dacMaxMin(int i, int j) {
        int max1, min1, mid;
        // Let a[0:n-1] be a global array.
        if (i == j) {
            max = min = array[i];
            // Small problem
        } else if (i == j - 1) {
            // Another case of small problem
            if (array[i] < array[j]) {
                max = array[j];
                min = array[i];
            } else {
                max = array[i];
                min = array[j];
            }
        } else {
            //If the problem is not small, divide it into subproblems.
            //Find where to split the set.
            mid = (i + j) / 2;
            // Solve the subproblems.
            dacMaxMin(i, mid);
            max1 = max;
            min1 = min;
            dacMaxMin(mid + 1, j);
            // Combine the solutions.
            if (max < max1) {
                max = max1;
            }
            if (min > min1) {
                min = min1;

            }
        }
    }

    public static void main(String[] a) {
        MaxMin m = new MaxMin(20);
        System.out.println("Contents of the Array");
        m.print();
        m.dacMaxMini();
        System.out.println("In this array maximum element : " + m.getMax());
        System.out.println("In this array minimum element : " + m.getMin());
    }
}

Output of this program is given bellow :


run:
Contents of the Array
38|36|37|35|37|29|31|35|37|28|28|29|29|34|35|38|29|38|32|37|
In this array maximum element : 38
In this array minimum element : 28
BUILD SUCCESSFUL (total time: 0 seconds)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .