Grade 10 · Divide and conquerCitește în română

Maximum of an array with divide and conquer

Original: Maximul unui vector prin divide et impera

O(n)C++1748 lines2 examples

The idea

The three stages of the method: we split the portion [st, dr] into two halves at the middle m = (st + dr) / 2 (divide); we find the maximum of each half recursively (conquer); the overall maximum is the larger of the two results (combine). The base case: a portion with a single element, which is its own maximum.

Original description (Romanian)

Cele trei etape ale metodei: împărțim porțiunea [st, dr] în două jumătăți, la mijlocul m = (st + dr) / 2 (divide); aflăm recursiv maximul fiecărei jumătăți (stăpânește); maximul total este cel mai mare dintre cele două rezultate (combină). Cazul elementar: o porțiune cu un singur element, care este chiar maximul ei.

Complexity
O(n), with stack depth O(log n)
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

6
4 9 2 17 5 8

Expected output

17
Example 2

Input

1
-3

Expected output

-3

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

maximul-unui-vector.cpp
/*
 * Titlu: Maximul unui vector prin divide et impera
 * Clasa: 10
 * Capitol: Divide et impera
 * Descriere: Cele trei etape ale metodei: împărțim porțiunea [st, dr] în două
 *            jumătăți, la mijlocul m = (st + dr) / 2 (divide); aflăm recursiv maximul
 *            fiecărei jumătăți (stăpânește); maximul total este cel mai mare dintre
 *            cele două rezultate (combină). Cazul elementar: o porțiune cu un singur
 *            element, care este chiar maximul ei.
 * Complexitate: O(n), cu adâncimea stivei O(log n)
 *
 * Exemplu
 * Intrare:
 * 6
 * 4 9 2 17 5 8
 * Ieșire: 17
 *
 * Exemplu
 * Intrare:
 * 1
 * -3
 * Ieșire: -3
 */
#include <iostream>
using namespace std;

int v[1000];

int maxim(int st, int dr)
{
    if (st == dr)
        return v[st];
    int m = (st + dr) / 2;
    int a = maxim(st, m);
    int b = maxim(m + 1, dr);
    return a > b ? a : b;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    cout << maxim(0, n - 1) << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.