Janela fixa — Soma máxima de subarray de tamanho 3:
Array: [2, 1, 5, 1, 3, 2]

  [2, 1, 5] 1, 3, 2    soma=8
   2 [1, 5, 1] 3, 2    soma=8-2+1=7
   2, 1 [5, 1, 3] 2    soma=7-1+3=9  ← máximo!
   2, 1, 5 [1, 3, 2]   soma=9-5+2=6

Janela variável — Menor subarray com soma >= 7:
Array: [2, 3, 1, 2, 4, 3]

  [2] soma=2 < 7, expande →
  [2, 3] soma=5 < 7, expande →
  [2, 3, 1] soma=6 < 7, expande →
  [2, 3, 1, 2] soma=8 >= 7, tamanho=4, contrai ←
  [3, 1, 2] soma=6 < 7, expande →
  [3, 1, 2, 4] soma=10 >= 7, tamanho=4, contrai ←
  [1, 2, 4] soma=7 >= 7, tamanho=3, contrai ←
  [2, 4] soma=6 < 7, expande →
  [2, 4, 3] soma=9 >= 7, tamanho=3, contrai ←
  [4, 3] soma=7 >= 7, tamanho=2 ← menor!

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Soma máxima de subarray de tamanho k (janela fixa).
pub fn somaMaximaJanelaFixa(arr: []const i32, k: usize) ?i64 {
    if (arr.len < k or k == 0) return null;

    // Soma da primeira janela
    var soma: i64 = 0;
    for (0..k) |i| soma += arr[i];

    var max_soma = soma;

    // Desliza a janela
    for (k..arr.len) |i| {
        soma += arr[i] - arr[i - k];
        max_soma = @max(max_soma, soma);
    }

    return max_soma;
}

/// Menor subarray com soma >= alvo (janela variável).
pub fn menorSubarrayComSoma(arr: []const i32, alvo: i32) ?usize {
    var esq: usize = 0;
    var soma: i64 = 0;
    var min_tam: usize = std.math.maxInt(usize);

    for (0..arr.len) |dir| {
        soma += arr[dir];

        while (soma >= alvo) {
            min_tam = @min(min_tam, dir - esq + 1);
            soma -= arr[esq];
            esq += 1;
        }
    }

    return if (min_tam == std.math.maxInt(usize)) null else min_tam;
}

/// Maior substring sem caracteres repetidos.
pub fn maiorSubstringSemRepeticao(s: []const u8) struct { tamanho: usize, inicio: usize } {
    if (s.len == 0) return .{ .tamanho = 0, .inicio = 0 };

    var ultimo: [256]i32 = undefined;
    @memset(&ultimo, -1);

    var esq: usize = 0;
    var max_tam: usize = 0;
    var max_inicio: usize = 0;

    for (0..s.len) |dir| {
        const c = s[dir];
        if (ultimo[c] >= 0 and @as(usize, @intCast(ultimo[c])) >= esq) {
            esq = @intCast(@as(usize, @intCast(ultimo[c])) + 1);
        }
        ultimo[c] = @intCast(dir);

        if (dir - esq + 1 > max_tam) {
            max_tam = dir - esq + 1;
            max_inicio = esq;
        }
    }

    return .{ .tamanho = max_tam, .inicio = max_inicio };
}

/// Média móvel de janela k.
pub fn mediaMovel(allocator: Allocator, arr: []const f64, k: usize) ![]f64 {
    if (arr.len < k) return try allocator.alloc(f64, 0);

    var resultado = try allocator.alloc(f64, arr.len - k + 1);

    var soma: f64 = 0;
    for (0..k) |i| soma += arr[i];
    resultado[0] = soma / @as(f64, @floatFromInt(k));

    for (k..arr.len) |i| {
        soma += arr[i] - arr[i - k];
        resultado[i - k + 1] = soma / @as(f64, @floatFromInt(k));
    }

    return resultado;
}

/// Máximo em cada janela de tamanho k usando deque.
pub fn maximoJanela(allocator: Allocator, arr: []const i32, k: usize) ![]i32 {
    if (arr.len < k) return try allocator.alloc(i32, 0);

    var resultado = try allocator.alloc(i32, arr.len - k + 1);
    var deque = std.ArrayList(usize).init(allocator);
    defer deque.deinit();

    for (0..arr.len) |i| {
        // Remove elementos fora da janela
        while (deque.items.len > 0 and deque.items[0] + k <= i) {
            _ = deque.orderedRemove(0);
        }
        // Remove elementos menores que o atual
        while (deque.items.len > 0 and arr[deque.items[deque.items.len - 1]] <= arr[i]) {
            _ = deque.pop();
        }
        try deque.append(i);

        if (i >= k - 1) {
            resultado[i - k + 1] = arr[deque.items[0]];
        }
    }

    return resultado;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Soma máxima de janela fixa
    const arr = [_]i32{ 2, 1, 5, 1, 3, 2 };
    if (somaMaximaJanelaFixa(&arr, 3)) |soma| {
        try stdout.print("Soma máxima (janela 3): {d}\n", .{soma});
    }

    // Menor subarray com soma >= 7
    const arr2 = [_]i32{ 2, 3, 1, 2, 4, 3 };
    if (menorSubarrayComSoma(&arr2, 7)) |tam| {
        try stdout.print("Menor subarray com soma >= 7: {d} elementos\n", .{tam});
    }

    // Maior substring sem repetição
    const texto = "abcabcbb";
    const sub = maiorSubstringSemRepeticao(texto);
    try stdout.print("Maior substring sem repetição em \"{s}\": \"{s}\" (tamanho {d})\n", .{
        texto, texto[sub.inicio .. sub.inicio + sub.tamanho], sub.tamanho,
    });

    // Máximo em cada janela
    const arr3 = [_]i32{ 1, 3, -1, -3, 5, 3, 6, 7 };
    const maximos = try maximoJanela(allocator, &arr3, 3);
    defer allocator.free(maximos);
    try stdout.print("Máximo em janela 3: ", .{});
    for (maximos) |m| try stdout.print("{d} ", .{m});
    try stdout.print("\n", .{});
}