Finding a maximum of a subarray

Asked Dec 12 '14 at 13:46

Active Dec 12 '14 at 13:46

Viewed 145 times

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Examples:

Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6

My code:

void printKMax(int arr[], int n, int k)
{
    int j, max;

    for (int i = 0; i <= n-k; i++)
    {
        max = arr[i];

        for (j = 1; j < k; j++)
        {
            if (arr[i+j] > max)
               max = arr[i+j];
        }
        printf("%d ", max);
    }
}

Time Complexity O(n^2) If there is some linear solution possible i.e of O(n) time complexity by using BIT Tree or using any other data structure and how can i expand my algorithm to find the no. of increasing sequence also.

asked Dec 12 '14 at 13:46

QWE

2

You could iterate from `[0]` to `[size - k]`, and then use [`std::max_element(arr + i, arr + i + k)`](http://www.cplusplus.com/reference/algorithm/max_element/) – Cory Kramer Dec 12 '14 at 13:48
re the main question, just use a multiset to reduce the thing to n log n. – Cheers and hth. - Alf Dec 12 '14 at 13:52
@Cheersandhth.-Alf did't get you please explain in brief – QWE Dec 12 '14 at 13:54
1

maintain a set of the values in the current segment. update the set incrementally when you move forward. each update is logarithmic in array size in the worst case. – Cheers and hth. - Alf Dec 12 '14 at 13:56
@Cheersandhth.-Alf i understand you intention , since the size of tree would be k i.e tree[k] and traditional trees is formed as tree[a[i]] , how i place the values – QWE Dec 12 '14 at 14:04
just use `std::multiset`? – Cheers and hth. - Alf Dec 12 '14 at 14:07
1

@Cheersandhth.-Alf would you please give me example how to store the value in tree – QWE Dec 12 '14 at 14:09
@QWE: wait a moment please – Cheers and hth. - Alf Dec 12 '14 at 14:16
I couldn't get Coliru to work, so, (http://ideone.com/b9eRoF). But it may be better to just go at things and figure them out yourself. – Cheers and hth. - Alf Dec 12 '14 at 14:40
@Cheersandhth.-Alf thanks for your effort that's really helpful will ping you back if i found any query – QWE Dec 12 '14 at 15:46

Finding a maximum of a subarray

0 Answers0