Subarray de suma máxima (Kadane)

def max_subarray(a):
    """Kadane con posiciones: (suma, inicio, fin) del tramo de suma máxima."""
    actual, ini = a[0], 0
    mejor, mejor_ini, mejor_fin = a[0], 0, 0
    for i in range(1, len(a)):
        if a[i] > actual + a[i]:                      # lo anterior resta: se empieza de nuevo aquí
            actual, ini = a[i], i
        else:
            actual += a[i]
        if actual > mejor:
            mejor, mejor_ini, mejor_fin = actual, ini, i
    return mejor, mejor_ini, mejor_fin


for a in [[-2, 1, -3, 4, -1, 2, 1, -5, 4], [5, -9, 6, -2, 3], [-3, -1, -2], [2, 3, -1, 4]]:
    suma, ini, fin = max_subarray(a)
    print(f"[{', '.join(map(str, a))}] → suma {suma} en [{ini}..{fin}]")

/** Kadane con posiciones: [suma, inicio, fin] del tramo de suma máxima. */
function maxSubarray(a) {
    let actual = a[0], ini = 0;
    let mejor = a[0], mejorIni = 0, mejorFin = 0;
    for (let i = 1; i < a.length; i++) {
        if (a[i] > actual + a[i]) {                   // lo anterior resta: se empieza de nuevo aquí
            actual = a[i];
            ini = i;
        } else actual += a[i];
        if (actual > mejor) {
            mejor = actual;
            mejorIni = ini;
            mejorFin = i;
        }
    }
    return [mejor, mejorIni, mejorFin];
}

for (const a of [[-2, 1, -3, 4, -1, 2, 1, -5, 4], [5, -9, 6, -2, 3], [-3, -1, -2], [2, 3, -1, 4]]) {
    const [suma, ini, fin] = maxSubarray(a);
    console.log(`[${a.join(", ")}] → suma ${suma} en [${ini}..${fin}]`);
}

using System;

class Program {
    /// Kadane con posiciones: {suma, inicio, fin} del tramo de suma máxima.
    static int[] MaxSubarray(int[] a) {
        int actual = a[0], ini = 0;
        int mejor = a[0], mejorIni = 0, mejorFin = 0;
        for (int i = 1; i < a.Length; i++) {
            if (a[i] > actual + a[i]) {                       // lo anterior resta: se empieza de nuevo aquí
                actual = a[i];
                ini = i;
            } else actual += a[i];
            if (actual > mejor) {
                mejor = actual;
                mejorIni = ini;
                mejorFin = i;
            }
        }
        return new[] { mejor, mejorIni, mejorFin };
    }

    static void Main() {
        int[][] casos = { new[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }, new[] { 5, -9, 6, -2, 3 }, new[] { -3, -1, -2 }, new[] { 2, 3, -1, 4 } };
        foreach (int[] a in casos) {
            int[] r = MaxSubarray(a);
            Console.WriteLine("[" + string.Join(", ", a) + "] → suma " + r[0] + " en [" + r[1] + ".." + r[2] + "]");
        }
    }
}

<?php
/** Kadane con posiciones: [suma, inicio, fin] del tramo de suma máxima. */
function maxSubarray(array $a): array {
    $actual = $a[0];
    $ini = 0;
    $mejor = $a[0];
    $mejorIni = 0;
    $mejorFin = 0;
    for ($i = 1; $i < count($a); $i++) {
        if ($a[$i] > $actual + $a[$i]) {              // lo anterior resta: se empieza de nuevo aquí
            $actual = $a[$i];
            $ini = $i;
        } else $actual += $a[$i];
        if ($actual > $mejor) {
            $mejor = $actual;
            $mejorIni = $ini;
            $mejorFin = $i;
        }
    }
    return [$mejor, $mejorIni, $mejorFin];
}

foreach ([[-2, 1, -3, 4, -1, 2, 1, -5, 4], [5, -9, 6, -2, 3], [-3, -1, -2], [2, 3, -1, 4]] as $a) {
    [$suma, $ini, $fin] = maxSubarray($a);
    echo "[" . implode(", ", $a) . "] → suma $suma en [$ini..$fin]\n";
}

n = 2000
a = []
x = 7
for i in range(n):                                    # números «aleatorios» que salen iguales en cualquier lenguaje
    x = (x * 75 + 74) % 65537
    a.append(x % 201 - 100)

sumas = 0
mejor_bruta = -10**9
for i in range(n):                                    # fuerza bruta: cada inicio, alargando el final
    s = 0
    for j in range(i, n):
        s += a[j]
        sumas += 1
        if s > mejor_bruta:
            mejor_bruta = s

actual = mejor = a[0]
for i in range(1, n):
    actual = max(a[i], actual + a[i])
    mejor = max(mejor, actual)
print(f"Fuerza bruta: {mejor_bruta} tras {sumas} sumas")
print(f"Kadane: {mejor} tras {n - 1} pasos")

const n = 2000;
const a = new Array(n);
let x = 7;
for (let i = 0; i < n; i++) {                         // números «aleatorios» que salen iguales en cualquier lenguaje
    x = (x * 75 + 74) % 65537;
    a[i] = x % 201 - 100;
}

let sumas = 0;
let mejorBruta = -Infinity;
for (let i = 0; i < n; i++) {                         // fuerza bruta: cada inicio, alargando el final
    let s = 0;
    for (let j = i; j < n; j++) {
        s += a[j];
        sumas++;
        mejorBruta = Math.max(mejorBruta, s);
    }
}

let actual = a[0], mejor = a[0];
for (let i = 1; i < n; i++) {
    actual = Math.max(a[i], actual + a[i]);
    mejor = Math.max(mejor, actual);
}
console.log(`Fuerza bruta: ${mejorBruta} tras ${sumas} sumas`);
console.log(`Kadane: ${mejor} tras ${n - 1} pasos`);

using System;

class Program {
    static void Main() {
        int n = 2000;
        int[] a = new int[n];
        int x = 7;
        for (int i = 0; i < n; i++) {                        // números «aleatorios» que salen iguales en cualquier lenguaje
            x = (x * 75 + 74) % 65537;
            a[i] = x % 201 - 100;
        }

        long sumas = 0;
        int mejorBruta = int.MinValue;
        for (int i = 0; i < n; i++) {                        // fuerza bruta: cada inicio, alargando el final
            int s = 0;
            for (int j = i; j < n; j++) {
                s += a[j];
                sumas++;
                mejorBruta = Math.Max(mejorBruta, s);
            }
        }

        int actual = a[0], mejor = a[0];
        for (int i = 1; i < n; i++) {
            actual = Math.Max(a[i], actual + a[i]);
            mejor = Math.Max(mejor, actual);
        }
        Console.WriteLine(
quot;Fuerza bruta: {mejorBruta} tras {sumas} sumas");
        Console.WriteLine(
quot;Kadane: {mejor} tras {n - 1} pasos");
    }
}

<?php
$n = 2000;
$a = [];
$x = 7;
for ($i = 0; $i < $n; $i++) {                         // números «aleatorios» que salen iguales en cualquier lenguaje
    $x = ($x * 75 + 74) % 65537;
    $a[] = $x % 201 - 100;
}

$sumas = 0;
$mejorBruta = PHP_INT_MIN;
for ($i = 0; $i < $n; $i++) {                         // fuerza bruta: cada inicio, alargando el final
    $s = 0;
    for ($j = $i; $j < $n; $j++) {
        $s += $a[$j];
        $sumas++;
        if ($s > $mejorBruta) $mejorBruta = $s;
    }
}

$actual = $mejor = $a[0];
for ($i = 1; $i < $n; $i++) {
    $actual = max($a[$i], $actual + $a[$i]);
    $mejor = max($mejor, $actual);
}
echo "Fuerza bruta: $mejorBruta tras $sumas sumas\n";
echo "Kadane: $mejor tras " . ($n - 1) . " pasos\n";