Find maximum of minimum for every window size in a given array

Given an integer array of size n, find the maximum of the minimum’s of every window size in the array. Note that window size varies from 1 to n.
Examples:
Input: arr[] = {10, 20, 30, 50, 10, 70, 30}
Output: 70, 30, 20, 10, 10, 10, 10

First element in output indicates maximum of minimums of all windows of size 1.
Minimums of windows of size 1 are {10}, {20}, {30}, {50}, {10}, {70} and {30}. Maximum of these minimums is 70

Second element in output indicates maximum of minimums of all windows of size 2.
Minimums of windows of size 2 are {10}, {20}, {30}, {10}, {10},
and {30}. Maximum of these minimums is 30

Third element in output indicates maximum of minimums of all windows of size 3.
Minimums of windows of size 3 are {10}, {20}, {10}, {10} and {10}.
Maximum of these minimums is 20

Similarly other elements of output are computed.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //Find maximum of minimum for every window size in a given array
            int[] arr = { 10, 20, 30, 50, 10, 70, 30 };
            //int[] arr = { 3, 2, 3, 1, 5, 6, 4, 5, 6 };
            int[] outputArray = new int[arr.Length];
            for(int windowLength = 1; windowLength <= arr.Length; windowLength++) //window size
            {
                int globalFlag = -1, maximum = 0;
                for (int startPos = 0; (startPos + windowLength) <= arr.Length; startPos++) //starting position
                {
                    int localFlag = -1, minimum = 0;
                    for (int iterator = startPos; iterator < (startPos + windowLength); iterator++)
                    {
                        //Get the minimum
                        if (localFlag == -1)
                        {
                            minimum = arr[iterator];
                            localFlag = 0;
                        } 
                        else
                        {
                            if(minimum > arr[iterator])
                            {
                                minimum = arr[iterator];
                            }
                        }
                    }
                    //Get the maximum of minimum
                    if(globalFlag == -1)
                    {
                        maximum = minimum;
                        globalFlag = 0;
                    }
                    else
                    {
                        if(maximum < minimum)
                        {
                            maximum = minimum;
                        }
                    }
                }
                outputArray[windowLength - 1] = maximum;
            }
            //Print the output array
            for(int i = 0; i < outputArray.Length; i++)
            {
                Console.Write(outputArray[i] + " ");
            }
            Console.WriteLine();
        }
    }
}

Output
=======
70 30 20 10 10 10 10
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s