Write a program that implement divide and conquer method to find the maximum and minimum of n elements.Use recursion to implement the divide and conquer scheme.

First we see what is divide and conquer method in computer science ? and implement divide and conquer method to find the maximum and minimum of n elements in java language.

What is divide and conquer method in computer science ?

Divide : divide the problem into a number of sub problems that are smaller instance of the same problem.

Conquer : conquer the sub problems by solving  them recursively.

Combine : combine the solution to the sub problems into the solution for the original problem.

now,lets implement divide and conquer method to find the maximum and minimum of n elements in java language.

 

public class MaxMin {
    static MaxMin m=new MaxMin();
    static int max,min;

    public static void main(String ar[])
    {
        int a[]={17,155,99,7,15,11,10,1};
        MaxMin.max=MaxMin.min=a[0];
        int[] getMaxMin=m.MaxMin(a, 0, a.length-1, a[0], a[0]);
        System.out.println("Max : "+getMaxMin[0]+"\nMin : "+getMaxMin[1]);
    }

    public int[] MaxMin(int[] a,int i,int j,int max,int min)
    {
        int mid,max1,min1;
        int result[]=new int[2];
        //Small(P)
        if (i==j) { max = min = a[i]; }
     else if (i==j-1) // Another case of Small(P)
          {
                if (a[i] < a[j]) { this.max = getMax(this.max,a[j]); this.min = getMin(this.min,a[i]); }
                else { this.max = getMax(this.max,a[i]); this.min = getMin(this.min,a[j]); }
          }
     else
     {
           // if P is not small, divide P into sub-problems.
           // Find where to split the set.
           mid = ( i + j )/2;
           // Solve the sub-problems.
           max1=min1=a[mid+1];
           MaxMin( a, i, mid, max, min );
           MaxMin( a, mid+1, j, max1, min1 );
           // Combine the solutions.
           if (this.max < max1) this.max = max1; if (this.min > min1) this.min = min1;
     }
        result[0]=this.max;  result[1]=this.min;
        return result;
    }

    public static int getMax(int i,int j)
    {
        if(i>j) return i;
        else return j;
    }

    public static int getMin(int i,int j)
    {
        if(i>j) return j;
        else return i;
    }
}

OUTPUT:
max-min

Leave a Reply