Maximum subarray (DP — Kadane / Subarray Sub-pattern)

// Kadane: cur = best sum of a subarray that ends exactly here.
// Either a[i] alone (restart) or the best one ending at i - 1, extended.
long long maxSubarray(const vector<int>& a) {
    long long cur = a[0], best = a[0];             // not 0: all-negative arrays need a real answer
    for (size_t i = 1; i < a.size(); i++) {
        cur = max((long long)a[i], cur + a[i]);    // extend or restart
        best = max(best, cur);
    }
    return best;
}