Tuesday, November 17, 2015

Find out maximum of subarry

Given an array and an size of sub array as k, find out maximum for every contiguous subarray of size k.
The problem looks simple but brute force would require n * k complexity to find out max in every subarray of length k.
We can improve complexity by introducing simple check as below 

  • First find max in array of length k.
  • For every next element in array post length k, check if its maximum than current max, if yer it becomes new max of current sub array.
  • If not then we need new max of current sub array... repeat step 2 & 3 this till end of array.
Worst case complexity of this approach would be n *k.
Code below implements this approach.


  
//Maximum of subarray
public class Solution {
    private static int FindMax(int[] input, int k, int start){
        if(start >= 0) {
            int max_index = start;
            for (int i = start; (i < input.length) && i < start + k; i++) {
                if (input[i] > input[max_index])
                    max_index = i;
            }
            return max_index;
        }
        return -1;
    }

    public static void MaxOfSubArrays(int [] input, int k) {
        if(input.length > k) {
            int max_index = FindMax(input, k, 0);
            int max = input[max_index];

            System.out.print(max + " ");

            for (int i = k; i < input.length; i++) {
                if (input[i] > max) {
                    max = input[i];
                    max_index = i;
                }
                else if (max_index <= i-k ) {
                    max_index = FindMax(input, k, i+1 - k);
                    max = input[max_index];
                }

                System.out.print(max + " ");
            }
        }
    }
    public static void main(String[] args){
        int [] input = {9, 8, 7, 6, 5, 12, 10, 3, 11};
        MaxOfSubArrays(input, 3);
    }
}
Comments are welcome.

No comments:

Post a Comment