Introduction to bruteforce

Brute force is a method where we try all possible options and choose the best valid one. It is simple but can be slow, so we use it only when the search space is small enough.

How Do We Brute Force?

Common patterns:

1. Nested loops
   • When number of variables is small and each has small range.
2. Bitmask enumeration
   • For subsets: for each mask from $0$ to $2^N-1$, check included elements.
3. Permutations
   • Use next_permutation in C++ to try all orderings.
4. Backtracking / recursion
   • Build solutions step by step and explore all possibilities (optionally with pruning).

Example 1: Maximum Sum of a Subarray of Length $K$

Given an array of $N$ integers and an integer $K$, find the maximum sum of contiguous subarray of length $K$.

Try every starting index $i$ from $0$ to $N-K$, sum $K$ elements starting at $i$, and keep the maximum.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    long long best = LLONG_MIN;

    // Brute force: try all subarrays of length K
    for (int i = 0; i + K <= N; i++) {
        long long sum = 0;
        for (int j = i; j < i + K; j++) {
            sum += a[j];
        }
        best = max(best, sum);
    }

    cout << best << endl;
    return 0;
}